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?

4 Years
Discussion Span
Last Post by FUTURECompEng

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?"

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.