Search code examples
time-complexitybig-ocomplexity-theorylogarithm

Solve for q: (log(n))^q = log(log(n))


I'm proving the big O runtime of an algorithm for an assignment but am unfortunately quite rusty when it comes to logs. Currently, I have:

(log(n))^q <= log(log(n))

I am trying to isolate q in terms of n (where I'm hoping n will cancel out). Can someone please explain to me how to do this (and not just provide an answer)? Thanks!


Solution

  • This would've been prettier on math stackexchange (because we can use latex), but you can just log both sides to bring the q exponent down (since log(x^n) = nlog(x) is a property of logs over the reals):

    q log(log(n)) <= log(log(log(n)))

    Now you can divide both sides to isolate q:

    q <= log(log(log(n)))/log(log(n))