CODEWITHSUNDEEP
algorithmrecursiontime-complexity
Matteo S.
Matteo S.

Reputation: 11

Time complexity of algorithm with multiple recursion

i'm trying to known time complexity about the following algorithms :

static int g(int[] a) {
  return g(a, 0, a.length-1);
}

static int g(int[] a, int i, int j) {
  if(i == j) return a[i];
  int onefourth = (j+1-i)/4;
  return g(a, i, i+onefourth) + g(a, i+onefourth+1, j);
}

This is my attempt :

The algorithm g(int[] a, int i, int j) split the dimension of array a by 4, and call recursively itself via multiple recursion. I can write the following recurrencies equation T(n) = T(n/4) + T(3n/4) + c = .... = T(n/4^k) + T(3n/4^k) + kc. Here, i have problem to choose a value of k. Anyone can help me ?

Upvotes: 0

Views: 1190

Answers (1)

btilly
btilly

Reputation: 46389

I don't know what techniques you were taught, but I know how I would figure this out from scratch.

When you divide the problem, apportion the cost of the recursive calls to the lower level proportionately to their sizes. Then ask the question of what the largest value is that could be apportioned to any value on the bottom.

Here is what I mean.

If you're looking at a range of length 1 you'll have some constant cost c.

If you're looking at a range of length 2 you'll have a constant recursion cost r divided evenly for a cost per element of c+r/2.

If you're looking at a range of length 3 the first element will get a cost of c + r/3 but the latter pair first gets 2/3 r at the top level, which is then split in 2 with another recursion cost for a total cost of c + r/2 + r/3.

And so on.

Now here is the challenge. What is the largest recursive cost that can be attributed to a particular call? Worst case somewhere in the chain is r for its level, plus 3/4 r for the level above it, plus (3/4)^2 r for the level above that, and so on. Can you find an upper bound?

Can you turn that upper bound into an upper bound on the cost attributed to a single element at the bottom?

Multiply that bound by the number of elements and you'll have your O(n).

Upvotes: 2

Related Questions