hey.. i attached the question and answer to the post
basically i understand everything outside of the black and red box.
black box: why are these two classes different ( O (nlogn) and O(n) )? is there a quick way to determine whether 5n + 2nlogn + 3 takes O(nlogn) or O(n)?
red box: how can you tell from looking at the function that it is between these two classes?
many thanks in advance. i have exams not far from now so any help is highly appreciated />
basic big Oh question, need some clarification
Page 1 of 12 Replies  1508 Views  Last Post: 24 April 2014  09:57 AM
Replies To: basic big Oh question, need some clarification
#2
Re: basic big Oh question, need some clarification
Posted 24 April 2014  07:01 AM
Note that O(n) is a subset of O(n log n). Noting the definition of BigO, n <= n log n, which implies that 1 < log(n), which is true. Note that log(n) is an increasing function.
So in order to determine if f(n) = O(g(n)), we take L = lim(n> infinity) f(n)/g(n). If L = 0, then f(n) = o(g(n)), which implies that f(n) = O(g(n)). Note that littleo is a strict inequality, while BigO is a weak inequality.
If 0 < L < infinity, then f(n) = Theta(g(n)). Otherwise, f(n) = omega(g(n)) => f(n) = Omega(g(n)). Again, littleomega is the strict inequality and BigOmega is the weak inequality.
So if we take lim(n> infinity) (5n + 2nlogn + 3)/(n log n) = lim(n > infinity) 5/log(n) + 2 + 3/(n log n) = 2. It converges to a constant, so 5n + 2nlogn + 3 = Theta(n log n).
For the red box question, we again note log(n) is an increasing function. So we consider f(n) = n log(n) log(n). Compare this to n log n, and we have f(n)/g(n) = log(n). So as we take a limit as n goes to infinity, we note that f(n)/g(n) tends to infinity. This implies that f(n) dominates g(n). Now if we consider lim(n>infinity) f(n)/n^{2}, we note the limit tends to 0. We are comparing log(n)log(n) to n, essentially. Also, by the definition of BigO, f(n) = O(n^{2}). So the phrase "between" implies that there is a tighter bound for f(n). However, O(n^{2}) is a valid bound.
So in order to determine if f(n) = O(g(n)), we take L = lim(n> infinity) f(n)/g(n). If L = 0, then f(n) = o(g(n)), which implies that f(n) = O(g(n)). Note that littleo is a strict inequality, while BigO is a weak inequality.
If 0 < L < infinity, then f(n) = Theta(g(n)). Otherwise, f(n) = omega(g(n)) => f(n) = Omega(g(n)). Again, littleomega is the strict inequality and BigOmega is the weak inequality.
So if we take lim(n> infinity) (5n + 2nlogn + 3)/(n log n) = lim(n > infinity) 5/log(n) + 2 + 3/(n log n) = 2. It converges to a constant, so 5n + 2nlogn + 3 = Theta(n log n).
For the red box question, we again note log(n) is an increasing function. So we consider f(n) = n log(n) log(n). Compare this to n log n, and we have f(n)/g(n) = log(n). So as we take a limit as n goes to infinity, we note that f(n)/g(n) tends to infinity. This implies that f(n) dominates g(n). Now if we consider lim(n>infinity) f(n)/n^{2}, we note the limit tends to 0. We are comparing log(n)log(n) to n, essentially. Also, by the definition of BigO, f(n) = O(n^{2}). So the phrase "between" implies that there is a tighter bound for f(n). However, O(n^{2}) is a valid bound.
#3
Re: basic big Oh question, need some clarification
Posted 24 April 2014  09:57 AM
Thinking about it less mathematically, you can look also look at which terms contribute more and piecewise, which one dominates. So for (5n + 2nlogn + 3), we can look at 5n, 2nlogn, and 3. Intuitively, the 2nlogn is going to grow the fastest since it is larger than the other two. Then a VALID upper bound would be O(nlogn), which literally means, given a c and an n_0, there exists a c*nlogn that when n > n_0, all values exceed the given function. More simply it upper bounds it.
You can take a similar approach for the other one in the black box.
The red, as Mac said can have an upper bound of n^2, but that is not the BEST upper bound. In addition, we can intutively see that nlogn is ALWAYS < n(logn)^2 for large values of n. Therefore, it is a sctrict lower bound (though again, there may be tighter bounds). Thus, it is safe to say that the runtime is BETWEEN O(nlogn) and O(n^2), though we have to do more analysis to find out exactly where it lies.
Again, for your formal proof, you should use limits, as mac said. But sometimes I find that the intuition coming first helps orchestrate how the proof is written.
You can take a similar approach for the other one in the black box.
The red, as Mac said can have an upper bound of n^2, but that is not the BEST upper bound. In addition, we can intutively see that nlogn is ALWAYS < n(logn)^2 for large values of n. Therefore, it is a sctrict lower bound (though again, there may be tighter bounds). Thus, it is safe to say that the runtime is BETWEEN O(nlogn) and O(n^2), though we have to do more analysis to find out exactly where it lies.
Again, for your formal proof, you should use limits, as mac said. But sometimes I find that the intuition coming first helps orchestrate how the proof is written.
Page 1 of 1
