O(n logn) vs O( n)

general
,
1

Which is more efficient ( O(n logn) or O( n) ) for a) smaller inputs b) larger inputs?

2

If you are asking the question in a general sense than, obviously O(n) is much better than O(n log(n)), thinking in terms of your question, then assuming

a) Smaller inputs n = 10^5

O(n log(n)) = O(10^5 * log(10^5) ) =
(10^5) *(5)

O(n) = O(10^5) = 10^5 (almost of the
same order).

b) Larger Inputs n = 10^9

O(n log(n)) = O(10^9log(10^9)) =
910^9

O(n) = O(10^9) = 10^9

9*(10^9) is much greater than 10^9.

Hope this helps!

Correct me if I’m wrong.

1 Like
3

It is a mistake when taken in the context that O(n) and O(n log n) functions have better complexity than O(1) and O(log n) functions. When looking typical cases of complexity in big O notation:

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

Notice that this doesn’t necessarily mean that they will always be better performance-wise - we could have an O(1) function that takes a long time to execute even though its complexity is unaffected by element count. Such a function would look better in big O notation than an O(log n) function, but could actually perform worse in practice.

Generally speaking: a function with lower complexity (in big O notation) will outperform a function with greater complexity (in big O notation) when n is sufficiently high.

note:- when n is high enough.

4

Yeah, 9*10^9 is nearly 10^10.

1 Like
5

I think that by “Smaller Input” he means n=100, 50 XD. At these cases, we need to consider the constant factor as well, as it starts playing a dominant role now.

PS: I just realized you took log to base 10. Its usually to the base 2. Eg, binary search is logN to base 2 not 10 :stuck_out_tongue: . Thats why i was wondering how did you get a very neat 5 x N term for O(NlogN) :stuck_out_tongue:

2 Likes
6

In a case where I apply merge sort and then apply binary search , what will be my total time complexity?

7

merge sort O(nlog(n) + log(n)*(number of times binary search)) = O(n log(n))

8

ohh… just for simplicity I take it that, just for understanding the purpose.

9

Actually this is not entirely correct. In most algorithms the log factor appears as a result of repeated division by 2, hence the base of the log should be 2 and not 10 when you’re trying to estimate the number of operations.
Then n \log n for n=10^5 is around 1.67 \times 10^6 and for n=10^9 it’s around 2.9 \times 10^{10}.

2 Likes