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?
Jump to PostI'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?"
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.
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?"
Thank you
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.