Is there a mistake in my solution for this recurrence?

[22990atinesh]

Homework Statement

$T(n) = 2 T(\frac{n}{2}) + 2$
$T(1) = 2$

Homework Equations

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

 

[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.

 

[22990atinesh]

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

 

[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:

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;
}

 

[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

 

[rcgldr]

How you are giving two solutions of the same recurrence relation
$T(1) = 2$

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.

 

[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.

 

[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

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

n = 6

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

n = 5

            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.

 

[22990atinesh]

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