Thread: 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;
}

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.

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

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.