Recursion Time Complexity Definition Confusion

user_9570941 0
Viewed 377

The time complexity of a recursive algorithm is said to be

Given a recursion algorithm, its time complexity O(T) is typically 
the product of the number of recursion invocations (denoted as R) 
and the time complexity of calculation (denoted as O(s)) 
that incurs along with each recursion 
O(T) = R * O(s)

Looking at a recursive function:

void algo(n){
  if (n == 0) return; // base case just to not have stack overflow
  for(i = 0; i < n; i++);// to do O(n) work 
  algo(n/2);
}

According to the definition above I may say that, the time complexity is, R is logn times and O(s) is n. So the result should be n logn where as with mathmetical induction it is proved that the result in o(n).

Please do not prove the induction method. I am asking why the given definition does not work with my approach.

recursion time-complexity
2 Answers

Great question! This hits at two different ways of accounting for the amount of work that's done in a recursive call chain.

The original strategy that you described for computing the amount of work done in a recursive call - multiply the work done per call by the number of calls - has an implicit assumption buried within it. Namely, this assumes that every recursive call does the same amount of work. If that is indeed the case, then you can determine the total work done as the product of the number of calls and the work per call.

However, this strategy doesn't usually work if the amount of work done per call varies as a function of the arguments to the call. After all, we can't talk about multiplying "the" amount of work done by a call by the number of calls if there isn't a single value representing how much work is done!

A more general strategy for determining how much work is done by a recursive call chain is to add up the amount of work done by each individual recursive call. In the case of the function that you've outlined above, the work done by the first call is n. The second call does n/2 work, because the amount of work it does is linear in its argument. The third call does n/4 work, the fourth n/8 work, etc. This means that the total work done is bounded by

n + n/2 + n/4 + n/8 + n/16 + ...

= n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

≤ 2n,

which is where the tighter O(n) bound comes from.

As a note, the idea of "add up all the work done by all the calls" is completely equivalent to "multiply the amount of work done per call by the number of calls" in the specific case where the amount of work done by each call is the same. Do you see why?

Alternatively, if you're okay getting a conservative upper bound on the amount of work done by a recursive call chain, you can multiply the number of calls by the maximum work done by any one call. That will never underestimate the total, but it won't always give you the right bound. That's what's happening here in the example you've listed - each call does at most n work, and there are O(log n) calls, so the total work is indeed O(n log n). That just doesn't happen to be a tight bound.

A quick note - I don't think it would be appropriate to call the strategy of multiplying the total work done by the number of calls the "definition" of the amount of work done by a recursive call chain. As mentioned above, that's more of a "strategy for determining the work done" than a formal definition. If anything, I'd argue that the correct formal definition would be "the sum of the amounts of work done by each individual recursive calls," since that more accurately accounts for how much total time will be spent.

Hope this helps!

user_5015570

I think you are trying to find information about master theorem which is what is used to prove the time complexity of recursive algorithms.

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

Also, you usually can't determine an algorithms runtime just from looking at it, especially recursive ones. That's why your quick analysis is different than the proof by induction.

user_56320360
Related