complexity of foo algorithm

I have this problem that I can't solve.. what is t开发者_如何学Pythonhe complexity of this foo algorithm?

int foo(char A[], int n, int m){
  int i, a=0;
  if (n>=m)
    return 0;
  for(i=n;i<m;i++)
    a+=A[i]  
  return a + foo(A, n*2, m/2);
}

the foo function is called by:

foo(A,1,strlen(A));

so.. I guess it's log(n) * something for the internal for loop.. which I'm not sure if it's log(n) or what..

Could it be theta of log^2(n)?

---

This is a great application of the master theorem:

Rewrite in terms of n and X = m-n:

int foo(char A[], int n, int X){
  int i, a=0;
  if (X < 0) return 0;
  for(i=0;i<X;i++)
    a+=A[i+n]  
  return a + foo(A, n*2, (X-3n)/2);
}

So the complexity is

T(X, n) = X + T((X - 3n)/2, n*2)

Noting that the penalty increases with X and decreases with n,

T(X, n) < X + T(X/2, n)

So we can consider the complexity

U(X) = X + U(X/2)

and plug this into master theorem to find U(X) = O(X) --> complexity is O(m-n)

---

I'm not sure if there's a 'quick and dirty' way, but you can use old good math. No fancy theorems, just simple equations.

On k-th level of recursion (k starts from zero), a loop will have ~ n/(2^k) - 2^k iterations. Therefore, the total amount of loop iterations will be S = sum(n/2^i) - sum(2^i) for 0 <= i <= l, where l is the depth of recursion.

The l will be approximately log(2, n)/2 (prove it).

Transforming each part in formula for S separately, we get.

S = (1 + 2 + .. + 2^l)*n/2^l - (2^(l + 1) - 1) ~= 2*n - 2^(l + 1) ~= 2*n - sqrt(n)

Since each other statement except loop will be repeated only l times and we know that l ~= log(2, n), it won't affect complexity.

So, in the end we get O(n).