In: Computer Science
Match the following functions to their respective big-O notation
1. 5 + 0.001n3 + 0.025n
2. 100nlog n + n5 + 100n
3. n2log n + nlog n
4. 2n + n5 + 5n
5. 100n + 0.01n2
A. |
O(n3) |
B. |
O(5n) |
C. |
O(n2) |
D. |
O(n5) |
E. |
O(n2log n) |
Ans ). Here's the matching.
1). 5 + 0.001n3 + 0.025n = A). O(n3) Since we can clearly see that the highest power is 3 and c*n3 will be an upper bound of the given polynomial for the appropriate choice of c.
2). 100nlog n + n5 + 100n = D). O(n5) Here also the largest or we can say the fastest growing term is n5, all the other terms say nlogn are smaller that this because we know logn is smaller than n. and therefore nlogn is smaller that n*n which is obviously smaller that n5.
3). n2log n + nlog n = E). O(n2log n) We can clearly see that larger term of the given function is n2log n.
4). 2n + n5 + 5n = B). O(5n) As we can see that we have an exponential term here and all the other terms are polynomial terms. Therefore here also 5n is clearly the major term.
5). 100n + 0.01n2 = C). O(n2) Here also we can see that n2 term is the largest among all the terms of the given function.
Hope it helps. Feel free to ask any doubts in commnets, I'll be more than happy to answer any of them. Don't forget to upvote if it helped :).