Big O / Running Time Example

[FUTURECompEng]

What is the running time for the following recursive function:

pubic static int Sum(int [] a, int start, int end) {
if ((end – start) = =0) 
return a[end]; 
else {
int mid = (end + start) / 2;
return (Sum(a, start,mid) + Sum(a,mid+1,end)); }
}

Can someone please explain step by step on how I would figure this out.

My attempt is that I only care about the if statement and int mid here (i think). "If" would be a simple n and would "int mid" be log_2n giving a running time of nlog_2n?

[deceptikon]

Can someone please explain step by step on how I would figure this out.

http://www.cs.duke.edu/~ola/ap/recurrence.html

"If" would be a simple n

It would be constant since the running time doesn't grow with N in any way.

[Momerath]

I'd look at it and say to myself "Hmm, starts with looking for the degenerate case of only 1 element, then if there are more partitions it into two parts, then recursively calls itself on these parts. What other well know algorithm does this and what's its Big O?"

[FUTURECompEng]

Thank you