On May 15, 9:04 pm, "amitabh chauhan" <[EMAIL PROTECTED]>
wrote:
> 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....-
> Hide quoted text -
>
> - Show quoted text -
Thank you for everyone. I understand.
Vinodh
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
