how is O(logm+logn) = O(log(m+n))? O is big oh.
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: how is O(logm+logn) = O(log(m+n))? O is big oh.

  1. #1
    Join Date
    Jan 2010
    Posts
    2

    how is O(logm+logn) = O(log(m+n))? O is big oh.

    Hi guys,

    Please help me understand this.
    The professor in my university says that.

    O(logm+logn) = O(log(m+n))?

    How is that?

    Thanks

  2. #2
    Join Date
    Nov 2003
    Posts
    1,819

    Re: how is O(logm+logn) = O(log(m+n))? O is big oh.

    Because they are both logarithmic time.

    gg

  3. #3
    Join Date
    Jan 2010
    Posts
    2

    Re: how is O(logm+logn) = O(log(m+n))? O is big oh.

    Thanks for the reply. But can you elaborate on that. I didnt understand.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: how is O(logm+logn) = O(log(m+n))? O is big oh.

    You expected O(log(M)+log(N)) to be equivalent to O(log(M*N)) right?

    It's true that log(M)+log(N) can be algebraically manipulated into log(M*N) but Big-O is not an algebra, it's a notation.

    O(log(M)+log(N)) expresses that the algorithm reacts logarithmically to M as well as to N. Regardless of which you vary or both, the algorithm will respond logarithmically. So the overall complexity is logarithmic and this is also expressed by O(log(M+N)). When M and N varies the overall response is logarithmic.

    Lets say that M and N varies together. Then you can replace M with N. In the first case you get

    O(log(N) + log(N)) = O(2*logN) = O(logN)

    And in the second case you have

    O(log(N + N)) = O(log(2*N)) = O(log(N))

    In Big-O both O(2*logN) and O(log(2*N)) expresses the same overall complexity, namely O(log(N)). You can multiply N with any constant, in Big-O notation it's still N. And you can multiply log(N) with any constant, it's still log(N).

    So Big-O notation characterizes algorithms in terms of broad complexity classes. In this case it says, this algorithm responds logarithmically to input so it's O(log(N)). It doesn't bother with different shades of logaritmicality. Logarithmic is logarithmic is logarithmic.
    Last edited by nuzzle; January 23rd, 2010 at 08:19 AM.

  5. #5
    Join Date
    Nov 2003
    Posts
    1,819

    Re: how is O(logm+logn) = O(log(m+n))? O is big oh.

    >> But can you elaborate...
    http://en.wikipedia.org/wiki/Big_O_notation

    gg

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center