COMP 250 Lecture 15: COMP250Lecture15Oct14BigO
18 Oct 2016
School
Department
Course
Professor
Document Summary
We want to express how some function, t(n), grows with n, as n becomes large. We want to compare the function with simpler functions such as log 2 (n), n, n 2 , 2 n , etc. t(n) is some complicated function (sum of terms and some constants, for example). The first idea is that these two functions cross at some point, n 0 . After that, t(n) will be less than g(n) forever. Notice that n 0 is not a unique point. Any bigger n 0 the same thing will hold. But the idea is we are looking past some point. Big o is what happens at large values of n. this is called asymptotic behavior. Let t(n) and g(n) be two functions, where n 0. We say t(n) is asymptotically bounded above by g(n) if there exists an n 0 such that, for all n n 0 , t(n) g(n) .
