You can find the solution here

This is a written homework assignment. It is due in class, in hard-copy.

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

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

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

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

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

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}\)
7. \(T(n) = \begin{cases} 3,& n\le 1\\ 1 + 2 T(n/2),& n\ge 2 \end{cases}\)
8. \(T(n) = \begin{cases} 1,& n\le 1\\ n + 2T(n/2),& n\ge 2 \end{cases}\)
9. \(T(n) = \begin{cases} 3,& n\le 1\\ 1 + 2 T(n-1),& n\ge 2 \end{cases}\)
10. \(T(n) = \begin{cases} 1,& n\le 2\\ 1 + nT(n-1),& n\gt 2 \end{cases}\)

• 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} \]