Menu
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?
456
So, O(N*log(N)) is far better than O(N^2) . It is much closer to O(N) than to O(N^2) . But your O(N^2) algorithm is faster for N < 100 in real life. There are a lot of reasons why it can be faster.
For the input of size n , an algorithm of O(n) will perform steps perportional to n , while another algorithm of O(log(n)) will perform steps roughly log(n) . Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.
The answer is no, for several reason: The expression O(f(n)) means that the running time is at most C f(n) with C a constant whose value is left undefined. It is well possible that the constant for O(log n) is much much larger than the one for O(n).
As we increase the input size 'n', O(1) will outperforms O(log n). Let's see an example, suppose n = 2048, now Code 1 will take 4 ms as it took previously but Code 2 will take 11 ms to execute. In this case, O(1) outperformed O(log n).
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.)
150
...because log n is always less than 1.
This is a faulty premise. In fact, logbn > 1 for all n > b. For example, log2 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.
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
