1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve this recurrence

  1. Nov 17, 2014 #1
    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. jcsd
  3. Nov 17, 2014 #2

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  4. Nov 17, 2014 #3
    Here is the original question and they way I'm solving it. Is there any other way for solving this question

    image.jpg

    image.jpg

    image.jpg
     
  5. Nov 17, 2014 #4

    rcgldr

    User Avatar
    Homework Helper

    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
  6. Nov 18, 2014 #5
    @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
     
  7. Nov 18, 2014 #6

    rcgldr

    User Avatar
    Homework Helper

    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
  8. Nov 18, 2014 #7
    @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.
     
  9. Nov 19, 2014 #8

    rcgldr

    User Avatar
    Homework Helper

    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
  10. Nov 21, 2014 #9
    @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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to solve this recurrence
Loading...