amitabh started his response fine, but strayed on the last line. Because of the change of base formula for logarithms, log_a(x) = log_b(x)/log_b(a), all logarithms are proportional.
Now let's look at the definition of big O notation: We say that f(x) = O(g(x)) as x --> oo if and only if there exist constants x0 > 0 and M > 0 such that |f(x)| <= M|g(x)| whenever x > x0. Thus, any constants in f(x) or g(x), including the constant of proportionality between logarithms, just change the value of the constant M, and so are swallowed up in the big O notation. Thus, O(log2 x) = O(ln x) = O(log10 x). It makes no difference what logarithm you use in big O notation. Dave On May 15, 6:52 am, "amitabh chauhan" <[EMAIL PROTECTED]> wrote: > actually base do not matters base 2 and base 10 are constant multiple of > each other so complexity remains same ( ya constant multiple do change )... > but its base 2 most often... --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
