ya i was only telling same thing .... rather proving it .... now i think his confusion is over ... enjoy!!
On 5/15/08, Dave <[EMAIL PROTECTED]> wrote: > > > 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 - > > > -- Amitabh S Chauhan life is like a box of chocolates. You never know what you're gonna get.... --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
