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

Question

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.

Answer 1

(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?)

EDIT:

On a related note, anybody who finds this question helpful and/or interesting should go show some love for the new "Computer Science" StackExchange site. Here's a link. Go make this new place a reality!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

Answer 2

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).

Answer 3

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.