Geek asks and answers

Is this feature complicated?

I am not sure about the following question:

Is log a(n b ) in O (log b(n a )) for constants a, b?

+3
source share
2 answers

When asked whether the function f (x) exists in O (g (x)), it really compares the growth rate of these two functions. (see wikipedia: http://en.wikipedia.org/wiki/Big_O_notation )

Constant function multipliers are ignored, so 2x is in O (x). Also, the components of the function with lower growth rates are similarly ignored, so 2x ^ 2 + x + 1 is in O (x ^ 2).

So the question is: does loga n ^ b have a similar growth rate like logb n ^ a?

, :

  • log x ^ b = b log x
  • loga x = (logb x)/(logb a)

, , O, , , , : O (logb n ^ a) = O (a logb n), - O-, : O (logb n).

, :

loga n ^ b = b loga n

, :

loga n ^ b = b (logb n)/(logb a)

:

loga n ^ b = (b/logb a) logb n

, (b/logb a) - , (b/logb a) logb n O (logb n)

, - . loga n ^ b O (logb n ^ a).

+5

b * log a (n), - * log b (n).

b * log (n)/log (a), - * log (n)/log (b).

, : " n 0 k , n > n 0, b * log (n)/log ( a) < k * a * log (n)/logb?"

: "... b/log (a) < k * a/log (b)?"

: "... b * log (b) < k * a * log (a)?"

, , "a" "b". "", b <= a.

+1

More articles:


All Articles