Using big-O notation

This is a discussion on Using big-O notation within the A Brief History of Cprogramming.com forums, part of the Community Boards category; How can I re-express the below thress functions of algorithm complexity using the big-O notation? 12 2n^2 + 3 n ...

  1. #1
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36

    Using big-O notation

    How can I re-express the below thress functions of algorithm complexity using the big-O notation?

    12
    2n^2 + 3 n
    5 n lg n + 4 n

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,975
    I havent studied complexity theory formally yet, but my guesses:

    12 => O(1)
    2n^2 + 3 n => O(n^2)
    5 n lg n + 4 n => O(n log n)
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    I think that the third one is O(n), but I'm not sure.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Registered User electRONix's Avatar
    Join Date
    Jun 2004
    Posts
    13

    this sounds like homework =d

    I'm taking a theory of algorithms class ...
    yeah the third one should be O(nlgn) since the nlgn part grows faster than the linear part. You always want to take the big O of what grows the fastest.. for example
    n + n^3 would be O(n^3)

    the first one is constant time so that is O(1) and the second one is quadratic time, O(nē) .. to be more precise there is also a theta function (for example while O(n) means the function is less than some constant times n, theta(n) means the function is just about the same as n. That's probably more detail then you needed so stick to
    O(1)
    O(nē) and
    O(nlgn)
    Last edited by electRONix; 06-06-2004 at 02:13 AM.
    my spider-sense be tingling.

    Ron - SCU Math/CS Major

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    You can take a quick limit to see which grows faster. That is, (n * lg n) / n = lg n which is unbounded as n grows. So, O(n lg n) > O(n).

  6. #6
    Registered User
    Join Date
    Jan 2003
    Posts
    648
    In general, take the highest order term in the polynomial, strip its coeficient and thats the Big-O efficiency. Remember, logarithms are exponents (inverse though) so this also applies for them.

  7. #7
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36
    for the third '5 n lg n + 4 n'

    since nlgn<n2<n3

    f(n)=5 n lg n + 4 n < 5(n3)+4n
    =19n

    am I correct?
    Last edited by alice; 07-05-2004 at 04:09 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,975
    hmm... I dont understand your reasoning.
    f(n) is 5n lg n + 4n
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    n3 should be n^3... That is, n cubed, not three times n

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 02:53 PM
  2. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  3. Big Oh notation, help me notate this
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-12-2005, 03:27 PM
  4. big o notation
    By heat511 in forum C++ Programming
    Replies: 5
    Last Post: 04-19-2002, 11:27 AM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM

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