Why is O(n) better than O( nlog(n) )?

Question

I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1. So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to take more time than n)

Does Big-O follow a different system?

Solution 1

It turned out, I misunderstood Logn to be lesser than 1. As I asked few of my seniors i got to know this today itself, that if the value of n is large, (which it usually is, when we are considering Big O ie worst case), logn can be greater than 1.

So yeah, O(1) < O(logn) < O(n) < O(nlogn) holds true.

(I thought this to be a dumb question, and was about to delete it as well, but then realised, no question is dumb question and there might be others who get this confusion so I left it here.)

Solution 2

...because log n is always less than 1.

This is a faulty premise. In fact, log_b n > 1 for all n > b. For example, log₂ 32 = 5.

Colloquially, you can think of log n as the number of digits in n. If n is an 8-digit number then log n ≈ 8. Logarithms are usually bigger than 1 for most values of n, because most numbers have multiple digits.

Solution 3

Plot both the graph( on desmos (https://www.desmos.com/calculator) or any other web) and look yourself the result on large values of n ( y=f(n)). I am saying that you should look for large value because for small value of n the program will not have time issue. For convenience I had attached a graph below you can try for other base of log.

The red represent time = n and blue represent time = nlog(n).

Solution 4

Here is a graph of the popular time complexities
n*log(n) is clearly greater than n for n>2 (log base 2)

An easy way to remember might be, taking two examples

1. Imagine the binary search algorithm: O(log(n))
2. For each step of binary search, you iterate the array of N elements
3. The result would be O(n*log(n))
4. Which is more work than iterating the array once: O(n)

Solution 5

In computers, it's log base 2 and not base 10. So log(2) is 1 and log(n), where n>2, is a positive number which is greater than 1. Only in the case of log (1), we have the value less than 1, otherwise, it's greater than 1.

View more solutions

Comments

[Jim Mischel]

"Usually the base is always less than 4." The base is neither usually nor always less than 4. In an [octree]en.wikipedia.org/wiki/Octree), for example,the base is 8. I'll grant that the most common data structures you'll work with in Computer Science classes will have a base of 4 or less, but the real world is different. In any case, the base is usually much smaller than the number of items you're considering when you talk about algorithmic analysis, so you can assume that log(n) will be greater than 1, regardless of the base.

[Naseem Ahamed]

It is not a dumb question at all! I have been confused about this until now. It looks like the key is the 'base'.