CODEWITHSUNDEEP
big-oproof
user1084113
user1084113

Reputation: 962

Big Oh Notation O((log n)^k) = O(log n)?

In big-O notation is O((log n)^k) = O(log n), where k is some constant (e.g. the number of logarithmic for loops), true?

I was told by my professor that this statement was true, however he said it will be proved later in the course. I was wondering if any of you could demonstrate its validity or have a link where I could confirm if it is true.

Upvotes: 6

Views: 8037

Answers (3)

Patrick87
Patrick87

Reputation: 28292

(1) It is true that O(log(n^k)) = O(log n).

(2) It is false that O(log^k(n)) (also written O((log n)^k)) = O(log n).

Observation: (1) has been proven by nmjohn.

Exercise: prove (2). (Hint: f(n) = log^2 n is O(log^2 n). Is it O(log n)? What is a sufficiently large constant c such that, for all n greater than n0, c log n > log^2 n?)

This is more of a CS question though. Future questions on this topic should be asked on the SE site.

Upvotes: 8

Michael Piefel
Michael Piefel

Reputation: 19968

O(log n) is a class of functions. You cannot perform computations such as ^k on it. Thus, the term O(log n)^k does not even look sensible to me.

Upvotes: -1

nmjohn
nmjohn

Reputation: 1432

Are you sure he didn't mean O(log n^k), because that equals O(k*log n) = k*O(log n) = O(log n).

Upvotes: 5

Related Questions