What would be the log(O(n * log(n)))?

0
votes

I am currently learning about big O notation in my algorithms class and I stumbled upon this particular problem that perplexed me. Can we represent O(n lg(n)) as c * n* lg n if we know the formal definition holds? Meaning, if f(n) <= cnlg n, and the definition holds true for some constants, then O(n lg n) can be represented as c* n* lg n? And if my assumption is true, then we could do:

= lg(O(n lg n))

= lg(c* n* lg n)

= lg(c) + lg(n) +lg(lg(n))

If lg(n) is the highest order term in this case, then would this simplify to be O(lg(n))? Since all the lower order terms would eventually be overlapped by the highest order term?

3
algorithmmathbig-o
As n grows arbitrarily large, the nlgn term will behave like a constant times n, so you would be left with lg(c*n). So I think your reasoning is correct. - Tim Biegeleisen
The problem you've posed is essentially nonsense. g(n) = O(f(n)) is an assertion about how fast g grows. O(.) isn't a function. So log(O(.)) is junk. - Gene
@Gene: Why do you think O is not a function? What is definition of a function? - Mangat Rai Modi
@MangatRaiModi A function is a relation, which is a set (often infinite) of ordered pairs (x,y) where x is taken from a set called the domain and y is from a set called the range. For each such pair, we can write f(x) = y. Try to identify a domain and range for big-O. You won't be able to. It's a different notation, which just happens to resemble function notation. - Gene
This question is probably better suited to CompSci.SE. - Will Vousden

3 Answers

2
votes

Yes, you are totally right and your math is correct.

enter image description here

2
votes

Your question is a little hard to follow. I think you are asking:

Suppose we have a function f that grows asymptotically at or less than a rate of O(n lg n). Does the function lg ∘ f grow asymptotically at or less than a rate of O(lg n)?

Yes, it does.

UPDATE: Commenter Paul Hankin points out a counterexample. Perhaps this is correct?

Suppose we have a function f that grows asymptotically at exactly a rate of O(n lg n). Does the function lg ∘ f grow asymptotically at a rate of O(lg n)?

I think the answer to that is yes.

0
votes

You're trying to show that lg(O(n lg n)) = O(lg n). This is somewhat non-standard notation, but it means that for all f in O(n lg n), there's a g in O(lg n) such that log(f) = g. This is explained on wikipedia here: https://en.wikipedia.org/wiki/Big_O_notation#Multiple_usages

The statement isn't quite true as written. For example, f = 2^(-n) is in O(n lg n), but lg(f) = -n which isn't in O(lg n). But if we limit ourselves to f's which are greater than 1, then it's true.

If f = O(n lg n), then there's a c such that for all sufficiently large n, f(n) < cn lg n. Then lg(f(n)) < lg(c) + lg(n) + lg(lg(n)) = O(lg n). Since lg(f(n)) > 0 , we have have that lg(f(n)) = O(lg n). This is essentially your proof from the question with a little additional care taken about definitions and making sure that lg(f(n)) isn't large and negative.