Big-O help

This is a discussion on Big-O help within the C++ Programming forums, part of the General Programming Boards category; I've looked all over the internet but I can't find an easy to understand an explanation of Big-O. I have ...

  1. #1
    mustang10
    Guest

    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];
    else
    return 0;
    }

  2. #2
    mustang10
    Guest
    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
    mustang10
    Guest
    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
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    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
    Posts
    1,385
    <shivers>

    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, 06: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

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