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.... --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
