Big Oh Notation problem

This is a discussion on Big Oh Notation problem within the C++ Programming forums, part of the General Programming Boards category; How can we write Code: O(V lg V+E lg V)=O(E lg V) V-No of vertices E-No of edges lg-log to ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    113

    Big Oh Notation problem

    How can we write
    Code:
    O(V lg V+E lg V)=O(E lg V)
    V-No of vertices
    E-No of edges
    lg-log to the base 2
    This is analysis of prim's algo.At the end of text this particular thing is given and I am not able to understand it.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,742
    Big-O only lists the most dominant term. Minor terms and constants are not shown in the final result.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Aug 2005
    Posts
    113
    But how can we say E>V?

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,742
    > But how can we say E>V?
    Isn't that in the preceding text?

    I'd say than in a graph, a single vertex can be the locus of many edges (at least two for a simple vertex with an edge in, and and edge out).

    Unless you have a really boring graph of two vertices and one edge, in which case the answer is pretty moot.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by vaibhav
    lg-log to the base 2
    Why even mention the base? It doesn't matter.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  2. I have big problem with encryption by ASCII
    By LINUX in forum C++ Programming
    Replies: 7
    Last Post: 04-29-2007, 01:46 PM
  3. polish notation calc problem
    By deedlit in forum C Programming
    Replies: 6
    Last Post: 06-14-2004, 11:17 PM
  4. Need Big Solution For Small Problem
    By GrNxxDaY in forum C++ Programming
    Replies: 8
    Last Post: 08-01-2002, 04:23 AM
  5. problem with pointer notation in for-loop
    By sballew in forum C Programming
    Replies: 5
    Last Post: 09-30-2001, 07:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21