For each of the program-snippets below, write the recurrence relations. You don't need to find the Big-0.

1. class Node {
       int data;
       Node next;
   }
   
   int football(Node first) {
       return football(first, 1);
   }
   
   int football(Node cur, int x) {
       if (cur == null) {
          System.out.println("Pinker Cake");
          return x;
       }
   
       x += football(cur.next, x);
       x += football(cur.next, x);
       return x;
   }
   

   SOLUTION:

   \(T(n) = \begin{cases} C_1 ,& n == 0 \\ C_2 + 2*T(n-1), & n > 0 \end{cases}\)

   EXPLANATION:

   We use n to refer to the length of the remaining list. In the base case, we do a constant amount of work, \(C_1\), however, in the recursive case, we make TWO recursive calls. The total amount of work there is \(2*T(n-1)\) where we are recursing down the list twice.

2. class Node {
       int data;
       Node next;
   }
   
   int college(Node first) {
       return college(first);
   }
   
   int college(Node cur){
       if (cur.next == null) {
          return 10;
       }
   
       return college(cur.next);
   }
   

   SOLUTION:

   \(T(n) = \begin{cases} C_1 ,& n == 0 \\ C_2 + T(n-1), & n > 0 \end{cases}\)

   EXPLANATION:

   We use n to refer to the length of the remaining list. In the base case, we do a constant amount of work, \(C_1\) and the recursive case we do more work \(C_2\) plus however much work we do in the recursive call with a list one shorter.

3. void usna(int[] arr) {
       usna(arr, arr.length);
   }
   
   void usna(int[] arr, int end) {
       if (end == 0) {
          return;
       }else{
          for (int i = 0; i < end; i++) 
             System.out.println("Go Navy!");
          usna(arr, end-1);
       }
   }
   

   SOLUTION:

   \(T(n) = \begin{cases} C_1 ,& n == 0 \\ n \cdot C_2 + T(n-1), & n > 0 \end{cases}\)

   EXPLANATION:

   We use \(n\) to refer to the end variable status. In the base case, we do a constant amount of work, \(C_1\), but in the recursive case we do a constant amount of \(C_2\) work \(n\) times, for \(n\cdot C_2\) amount of work, plus the work we'll do in the next recursive call \(T(n-1)\).

4. void usma(int[] arr) {
       usma(arr, arr.length);
   }
   
   void usma(int[] arr, int end) {
       if (end == 0) {
          return;
       }else{
          for (int i = 0; i < end*end; i++) 
             System.out.println("Beat Army!");
          usma(arr, end-1);
       }
   }
   

   SOLUTION:

   \(T(n) = \begin{cases} C_1 ,& n == 0 \\ n^2 \cdot C_2 + T(n-1), & n > 0 \end{cases}\)

   EXPLANATION:

   We use \(n\) to refer to the end variable status. In the base case, we do a constant amount of work, \(C_1\), but in the recursive case we do a constant amount of \(C_2\) work \(n^2\) times, for \(n\cdot C_2\) amount of work, plus the work we'll do in the next recursive call \(T(n-1)\).

5. void airforce(int[] arr) {
       airforce(arr, 0, arr.length);
   }
   
   void airforce(int[] arr, int beg, int end) {
       if ((end-beg) == 1) {
         System.out.println("Crash Air Force!");
         return;
       }
       else {
          int mid = (end+beg)/2;
          airforce(arr, beg, mid);
          airforce(arr, mid, end);
       }
   }
   

SOLUTION:

\(T(n) = \begin{cases} C_1 ,& n == 1 \\ C_2 + 2T(n/2), & n > 1 \end{cases}\)

EXPLANATION:

Here, \(n\) is the difference between the beg and end, and that is reducing by half each time, thus the \(n/2\), but we also recurse twice. That means in the recursive case, it cost \(2T(n/2)\). In the base case, it is constant amount of work when \(n=1\).

Find the Big-O of the following recurrence relations. Show your work. It might be helpful to try them on certain smallish values of n just to make sure you are right.

6. \(T(n) = \begin{cases} 10,& n\le 2 \\ 4 + T(n-1),& n \ge 3 \end{cases}\)

   SOLUTION: \(O(n)\)

   Expand the series and rewrite in terms of \(i\):

   \(T(n) = 4 + T(n-1) = 4 + 4 + T(n-2) = 4i + T(n-i)\)

   When \(i=(n-2)\) reach base case, substitute in

   \(4(n-2) + T(2) = 4(n-2) + 10 = O(n)\)

7. \(T(n) = \begin{cases} 3,& n\le 1\\ 1 + 2 T(n/2),& n\ge 2 \end{cases}\)

   SOLUTION: \(O(n)\)

   Expand the series and rewrite in terms of \(i\):

   \begin{array}[] TT(n) &= 1 + 2T(n/2) \\ &= 1 + 2(1 + 2T(n/4) &= 1 + 2 + 2^2T(n/2^2)\\ &= 1 + 2 + 2^2(1 + 2T(n/2^3)) &= 1 + 2 + 2^2 +2^3T(n/2^4)\\ &= \ldots \\ \end{array}

   \[ T(n) = \sum_{j=0}^{i-1} 2^j + 2^i \cdot T\left(\frac{n}{2^i}\right) \]

   Solve for i to reach base case:

   \begin{array}[] \frac{n}{2^i} &\le 1\\ n &\le 2^i\\ lg(n) &\ge i \end{array}

   Substitute in \(lg(n)\) for i

   \[ T(n) = \sum_{j=0}^{lg(n)-1} 2^j + 2^lg(n) \cdot T\left(\frac{n}{2^lg(n)}\right) \\ T(n) = \sum_{j=0}^{lg(n)-1} 2^j + n \cdot T(1) \\ T(n) = \sum_{j=0}^{lg(n)-1} 2^j + 3n\\ \]

   To solve the summation, we substitute \(lg(n)\) into the solution for a geometric series:

   \[ \sum_{j=0}^{lg(n)-1} 2^j = \frac{1 - 2^{lg(n)}}{1-2} = \frac{1-n}{-1} = n-1 \]

   This leaves us with:

   \[ T(n) = n-1 + 3n = 4n-1 = O(n) \]

8. \(T(n) = \begin{cases} 1,& n\le 1\\ n + 2T(n/2),& n\ge 2 \end{cases}\)

   SOLUTION: O(n log(n))

   Expand the series, solve with \(i\)

   \begin{array}[] TT(n) &= n + 2T(n/2) \\ &= n + 2(n/2 + 2T(n/4) &= n + n + 2^2T(n/2^2)\\ &= n + n + 2^2(n/2^2 + 2^2T(n/2^3)) &= n + n + n +2^4T(n/2^4)\\ &= \ldots \\ \end{array}

   \[ T(n) = n(i-1) + 2^i \cdot T\left(\frac{n}{2^i}\right) \]

   From question 7, we know that solution for \(i\) to reach base case is \(lg(n)\). We also know the solution to the summation as \(n-1\), so we can solve this like so:

   \[ T(n) = n(lg(n)-1) + 2^{lg(n)} = n \cdot lg(n) - n + n = O(n \log(n)) \]

9. \(T(n) = \begin{cases} 3,& n\le 1\\ 1 + 2 T(n-1),& n\ge 2 \end{cases}\)

   SOLUTION: O(2ⁿ)

   Expand the series, solve with \(i\)

   \begin{array}[] TT(n) &= 1 + 2T(n-1) \\ &= 1 + 2(1+2T(n-2) &= 1 + 2 + 2^2T(n-2)\\ &= 1 + 2 + 2^2(1+2T(n-3)) &= 2^0 + 2^1 + 2^2 +2^3T(n-4)\\ &= \ldots \\ \end{array}

   \[ T(n) = \sum_{j=0}^{i-1} 2^j + 2^i \cdot T(n-i) \]

   What value of \(i\) reaches the base case? That happens \(n-i = 1\) or \(i=n-1\). Substituting that into the solution from before.

   \[ T(n) = \sum_{j=0}^{n-2} 2^j + 2^{n-1} \cdot T(1)\\ T(n) = \sum_{j=0}^{n-2} 2^j + 2^{n-1} \]

   Already, you can see that there is 2ⁿ factor, so we could stop here. However, let's go all the way and solve the summation:

   \[ \sum_{j=0}^{n-2} 2^j = \frac{1 - 2^{n-1}}{1-2}= 2^{n-1} - 1 \]

   This leaves us with: \[ T(n) = 2^{n-1} - 1 + 2^{n-1} = 2^n-1 = O(2^n) \]

10. \(T(n) = \begin{cases} 1,& n\le 2\\ 1 + nT(n-1),& n\gt 2 \end{cases}\)

    SOLUTION: \(O(n!)\) or \(O(n^n)\)

    Expand the series, solve with \(i\)

    \begin{array}[] TT(n) &= 1 + nT(n-1) \\ &= 1 + n(1+(n-1)T(n-2)) &= 1 + n + n(n-1)T(n-2)\\ &= 1 + n + n(n-1)(1+(n-2)T(n-3)) &= 1 + n + n(n-1) +n(n-1)(n-2)T(n-3)\\ &= 1 + n + n(n-1) + n(n-1)(n-2)(1+(n-3)T(n-4)) &= 1 + n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-3)T(n-4)\\ &= \ldots \\ \end{array}

    The series is a factorial and there are n of them!

    \[ T(n) = \sum_{j=0}^{n} n!/j! = n! \sum_{j=0}^{n} 1/j! \]

    This leaves us with a large factor of \(n!\) multiplied by the series of \(1/i!\), which turns out to equal \(e\), the natural constant! So we have \(e\cdot n!\) which gives os \(O(n!)\).

    It's hard to describe just how LARGE \(n!\) is, but it is upper bounded by \(O(n^n)\) and lower bounded by \(\Omega(2^n)\). So this grows very, very fast.

• Arithmetic Sum

  \[ \sum_{i=1}^{n} i = n(n+1)/2 \]

• Geometric Sums

  \[ \sum_{i=0}^{n-1} r^i = \frac{1-r^n}{1-r} \]