Search code examples
time-complexityasymptotic-complexitybig-o

Theta Notation for N to the Power of Log Manipulation

In Asymptotic Notations for Order of Growth; Is the form 

Theta(N ^ ( ( LOGb( a / b) + 1 ) ) )

Equivalent to 

Theta(N ^ (LOGb( a ) ) ) ??

Where LOGb(a) means LOG a to base b.

Solution

  • Since log(a/b) = log a - log b and LOGb(b) = 1, we have LOGb(a/b)-1 = LOGb(a) - 1 + 1 = LOGb(a). No mention of asymptotics necessary, this equality is exact for all a, b > 0.