Big -O notation

Hey i have a question. say t(n) = O(n log(n)) and u know that this is开发者_开发百科 true.

and then your given these statements and told to say whether they must be true or false. t(n) = n^4 and t(n) = O(N^4)

The statement t(n) = n^4 is false while the statement t(n) = O(N^4) is true. Why?

---

You have to remember that when you write t(n) = O(n log(n)) and t(n) = O(N^4), what it actually means is that t(n) is in O(...), not that it's equal to it (as O(...) is a set of functions and a function can not be equal to a set of functions). However when you write f(n) = n^4, that means that f(n) is equal to n^4.

Now if f(n) is in O(n log n), it is also in O(n^4) because O(n^4) is a superset of O(n log n). However it can not be equal to n^4, because n^4 is not in O(n log n).

---

The idea of Big O notation is that it represents an abstracted function of time, it focuses on the slowest part of your algorithm and ignores things that affect execution time (i.e. t(n)) but don't actually make a huge difference.

For exmaple, if your function works on a set of items of size n and just loops through them performing some calculations then you'd say t(n) = O(n). Say you performed some operation only on a few of elements according to some criteria, you would still still say t(n) = O(n) but the actual time taken t(n) would not be a function of n directly, hence t(n) = nx would not hold true.

---

Look at the second equation in this. From this equation, t(n) = n^4 = O(n^4) is obvious.

t(n) = O(n log n) is false, because ∀M>0,x, ∃n>x, t(n) = n^4 > M(n log n). (if n > log n and n>M, n^4 > M*n^3 = M(n * n^2) > M(n * log n) = M(n log n), and n>log n when (roughly) n>5)