Looking for a good source

This is a discussion on Looking for a good source within the C++ Programming forums, part of the General Programming Boards category; I'm working on homework assignments for my C++ class, and one major part of many assignments is Big-O notation . ...

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    10

    Looking for a good source

    I'm working on homework assignments for my C++ class, and one major part of many assignments is Big-O notation. My problem is that I just don't get it. Are there any really good sources that gives a "for dummies" approach to Big-O notation?

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    I think the one on this very site is quiet good. I actually understood most of it from here, and them just filled in the blanks from a few google searches.

    http://www.cprogramming.com/tutorial...ficiency1.html
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    My problem is that I just don't get it.
    The general idea is that some things get waaaay more complicated as the number of "things" increases.

    For example, if you want to sort a list of names into alphabetical order - It might take more than twice as long to sort 20 names as it does to sort 10 names... How much longer? Big-O will tell you.

    That's just the general idea to get you started... If you turn that in for your homework, you might get a 'D'... if you are lucky.

  5. #5
    Registered User
    Join Date
    Aug 2006
    Posts
    10
    That's a helpful explanation actually. Thank you for that.

    I want to make one thing clear. My homework isn't "What is Big O?" Rather it is "using Big O, determine the complexity of C++ function T." I'm not looking for anyone to do function T for me. I just want to know how to do Big O. I hope that helps everyone know where I'm coming from.

    Hypothetical situation:
    Let's say I have a vector of 20 random integers (non-sorted) and I need to perform a selection sort on it. How would a programmer go from this given information, and do a Big O analysis?

  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Well first he would need to look at the source code itself, or at least have an idea of how a selection sort is performed. Nothing like having the actual code in front of him or some equivalent pseudo-code to better visualize the algorithm.

    Then he just follows the steps delineated on the link I provided you with earlier.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 'Type' Error on Build of Officially Released Source Code
    By Jedi_Mediator in forum C++ Programming
    Replies: 5
    Last Post: 07-07-2008, 06:28 PM
  2. Open Source and Security
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 06-17-2008, 02:23 AM
  3. To find the memory leaks without using any tools
    By asadullah in forum C Programming
    Replies: 2
    Last Post: 05-12-2008, 08:54 AM
  4. Source file inclusion
    By sh3rpa in forum C++ Programming
    Replies: 7
    Last Post: 10-02-2007, 12:10 PM
  5. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 03:53 PM

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