You are agreeing with my reply, arent' you? It appears that all you have done is introduce a derivation of the change of base formula that I mentioned.
The point I was trying to make is that if someone thinks that the base of the logarithm matters, then either he doesn't understand logarithms or he doesn't understand big O notation. O(n log n) means exactly the same thing no matter what the base of the logarithm. Dave On May 15, 8:59 am, "amitabh chauhan" <[EMAIL PROTECTED]> wrote: > i was saying that most often it happens that its base is 2 ... as it is > there on binary search and all .... as your size is always reducing to half > ... and like others ...... > > now by saying that it to not matter i want to say following proof :- > > let us have log with base x represented by logxn and log with base y > represented by logyn ..... > > then if we take logxn = p ........ (1) > and logyn = q ....... (2) > > then n= x^p > and n = y^q > > that means x^p = y^q > > or in other taking log both sides > > p * logx= q*logy ..... (3) > > by 1 and 2 above 3 becomes > > logxn*logx = logyn*logy > > also logx and logy are constant ...... > > hence say logx=c1 and logy = c2 > then c1*logxn = c2 * logyn > > or simply saying logxn = clogyn > hence constant multiple of each other ...... > > its a very common thing ..... and for more detail see any basic data > structure book like tanenbaum > > On 5/15/08, Dave <[EMAIL PROTECTED]> wrote: > > > > > > > > > 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... > > -- > Amitabh S Chauhan > life is like a box of chocolates. You never know what you're gonna get....- > Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
