# How to solve this recurrence

Tags:
1. Nov 17, 2014

### 22990atinesh

1. The problem statement, all variables and given/known data
$T(n) = 2 T(\frac{n}{2}) + 2$
$T(1) = 2$

2. Relevant equations

3. The attempt at a solution
I'm coming up with $T(n) = n-1$ on solving it by recursion tree method. But that's not the ans

2. Nov 17, 2014

### rcgldr

I'm not sure of what methods are expected to solve these type of equations. In this case though, you can calculate T for n_(i+1) = 2n_(i): T(1) = 2, T(2) = 6, T(4) = 14, T(8) = 30, ... , then you can look for a linear equation that produces the same results.

3. Nov 17, 2014

### 22990atinesh

Here is the original question and they way I'm solving it. Is there any other way for solving this question

4. Nov 17, 2014

### rcgldr

Find min and max of array of size n, by recursively splitting the array until subarray size == 2 and doing a single compare and returning the min and max. If subarray size == 1, return min = max = array[0], no compare. For each pair of returned (min, max) from two sub-arrays, do one compare for the two min's and one compare for the two max's.

The recurrence formula T(1) = 2, T(n) = 2T(n/2) + 2 = 4n - 2 as previous posted, but this doesn't represent the number of compares if you recursively split the array, since T(2) = 1 (only one compare needed to determine min and max with just two numbers). So by recursively splitting the array:

T(2) = 1, T(n) = 2T(n/2) + 2 = ⌈ 3n/2 ⌉ - 2.

Example code:
Code (Text):

typedef struct{
unsigned int min;
unsigned int max;
}MINMAX;

static size_t cmp;              // number of compares (optional global)

MINMAX findminmax(int a[], size_t sizea)
{
MINMAX minmax;
MINMAX minmaxl;
MINMAX minmaxr;
size_t sizea2;

if(sizea == 0){             // if empty array (can only happen on initial call)
minmax.min = 0;         //   set min = max = 0
minmax.max = 0;
return minmax;
}
if(sizea == 1){             // if size == 1
minmax.min = a[0];      //   set min = max = a[0]
minmax.max = a[0];
return minmax;
}
if(sizea == 2){             // if size == 2
if(a[0] <= a[1]){       //   set min and max
minmax.min = a[0];
minmax.max = a[1];
} else {
minmax.min = a[1];
minmax.max = a[0];
}
cmp += 1;
return minmax;
}

sizea2 = sizea/2;           // recursively split array, set min and max
minmaxl = findminmax(&a[0], sizea2);
minmaxr = findminmax(&a[sizea2], sizea - sizea2);
minmax.min = minmaxl.min <= minmaxr.min ? minmaxl.min : minmaxr.min;
minmax.max = minmaxl.max >= minmaxr.max ? minmaxl.max : minmaxr.max;
cmp += 2;
return minmax;
}

Last edited: Nov 17, 2014
5. Nov 18, 2014

### 22990atinesh

@rcgldr
How you are giving two solutions of the same recurrence relation
$T(n) = 2T(\frac{n}{2}) + 2$
$T(1) = 2$
as $4n-2$ and $\lfloor \frac{3n}{2} \rfloor - 2$
and what method are you using. If I use Master theorem, I'm coming up with the ans n and with recursion tree method n-1

6. Nov 18, 2014

### rcgldr

The recurrence relation is the same, but instead of T(1) = 2, it should be T(2) = 1, and this changes the result from 4n-2 to ⌈ 3n/2 ⌉ - 2. (Note its ceiling (round up), not floor). T(2) = 1, because if a subarray only has 2 elements, then it only takes 1 compare to determine which is the minimum and which is the maximum. This result matches the compare count in the example code posted above.

Last edited: Nov 18, 2014
7. Nov 18, 2014

### 22990atinesh

@rcgldr
hmm Sorry $T(2) = 1$ is correct. But still as you can see from the Pic that I've provided, that I'm getting $n - 1$ with recursion tree method. Could you please point out the msitake that I'm using.

8. Nov 19, 2014

### rcgldr

I''m not sure how to do a recursion tree except for specific cases. Powers of 2 are easiest, for example 8. The bottom row has no numbers (you need to compare pairs). The next to bottom row will have 1's, and all the rows above it will have 2's.

n = 8
Code (Text):

2
2           2
1     1     1     1
x x   x x   x x   x x

n = 6
Code (Text):

2
2           0
1     1     1
x x   x x   x x

n = 5
Code (Text):

2
2           0
1     1     0
x x   x x   x

Also answer b should have been written as "at most ⌈ 1.5 n ⌉ - 2 compares" are needed. It left out the part about rounding up if n is odd.

Last edited: Nov 19, 2014
9. Nov 21, 2014

### 22990atinesh

@rcgldr
Thanx got it. I was doing one algebraic mistake, thats why I was always ending up with $n - 1$
$\frac{3}{2} n - 2$ is correct