I saw a proof for O(2n) is same as O(n) in this post => Which algorithm is faster O(N) or O(2N)? Which means O(n) is same as O(4n).
Can someone show me how O(n) is not a subset of O(n log n)?
Because, if n = 16 and base = 2, O(n log n) will be O(n * 4), which should make it O(n)?
I know above statement is wrong. But not sure which part. Kindly clarify.
Because, if n = 16 and base = 2, O(n log n) will be O(n * 4), which should make it O(n)?
This is a fundamental misunderstanding of what O(n log n) means.
O(n log n) is a set of functions. Intuitively, it is the set of all functions {g(n)} where g(n) is proportional to f(n) = n log n.
(There is a rigorous mathematical definition of what "proportional" means that deals with awkward edge cases, but you need to understand "limits" ... which is relatively advanced mathematics ... to comprehend the definition.)
You are substituting a value for the argument ... which is mathematically meaningless. Facially, you are evaluating O(n log n) as a function for some value of n. That might make sense if O(...) denoted a function. But it doesn't.
Big O is a mathematical notation for a set of functions that are related to a given function in a particular way. And (intuitively) the relationship is about what happens when the n gets larger. You can substitute a specific value for n and still preserve the meaning of the notation.
(What you have done makes about as much mathematical sense as canceling out the x in:
d(x.x)
------
dx
... or one of those schoolboy "proofs" that one is zero that entails division by zero.)
To gain a deeper understand of why your substtution is meaningless, review the more formal definition of Big Oh notation; e.g. on Wikipedia. If you know what limits are.