Thread: Big-O help

  1. #1

    Big-O help

    I've looked all over the internet but I can't find an easy to understand an explanation of Big-O. I have the following problem for homework and the book doesn't explain it well enough for me to understand. I only have to figure out the following line but have added the rest of the code also. My initial guess is O(N^2).
    return sum (a, start, mid) + sum (a, mid+1, end);

    int sum (int a[], int start, int end)
    if (start < end)
    int mid = (start + end) /2;
    return sum (a, start, mid) + sum (a, mid+1, end); //only line to count

    else if (start ==end)
    return a [start];
    return 0;

  2. #2
    Thanks Salem. I use that site regularly to look up definitions. I still don't understand how to apply the formula to a line of code. If I could see an example it would help.

  3. #3
    Salem... after reading that page it still seems like jibberish to me.
    since I only have to do the 1 line would it be the first sum takes A millisec to accomplish + the second sum which would take B millisec to accomblish. That gives you A + B? Is this how you read it? Thanks for the help

  4. #4
    Registered User
    Join Date
    May 2003
    mustang, try to figure out the following:

    Assume N is 10 (there are 10 numbers between start and end). How many times is your function called?

    Now assume N is 100, how many times is it called now?

    It's better than O(N^2), I can guarantee that. And the best case scenario for any summation is O(N), so anything lower (e.g. O(1) or O(logN)) is impossible.

  5. #5
    Hamster without a wheel iain's Avatar
    Join Date
    Aug 2001

    i remeber big-o from first year at uni, erghh!!
    Monday - what a way to spend a seventh of your life

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How Big is Too Big
    By kpreston in forum C Programming
    Replies: 4
    Last Post: 10-25-2008, 10:16 AM
  2. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 07:07 PM
  3. Big help for big program
    By Mahesh in forum C Programming
    Replies: 1
    Last Post: 05-04-2005, 10:02 AM
  4. Adding to a big char* for search engine
    By Landroid in forum C Programming
    Replies: 5
    Last Post: 03-03-2005, 07:16 PM
  5. Looking for some big C/C++ projects
    By C-Dumbie in forum C Programming
    Replies: 5
    Last Post: 09-16-2002, 12:18 AM