Write your answers to the following on a separate piece of paper.

For each of the program-snippets below, write the recurrence relations for the public method.

You don’t need to find the Big-0, just write the recurrence relation.

1. private class Node {
       int data;
       Node next;
   }
   
   private Node head;
   
   public int football() {
       return football(head, 1);
   }
   
   private int football(Node cur, int x) {
       if (cur == null) {
          System.out.println("Some words!");
          return x;
       }
   
       x += football(cur.next, x);
       x += football(cur.next, x);
       return x;
   }
   

   
   

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

3. public void usna(int[] arr) {
       usna(arr, arr.length);
   }
   
   private 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. public void usma(int[] arr) {
       usma(arr, arr.length);
   }
   
   private 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. public void airforce(int[] arr) {
       airforce(arr, 0, arr.length);
   }
   
   private 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 3\\ 1 + 2T(\sqrt{n}),& n\ge 4 \end{cases}\)

Some useful formulas that you should know

• Sum of consecutive integers (arithmetic):

  \[1 + 2 + 3 + 4 + \cdots + n = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}\]

• Sum of powers of 2 (geometric):

  \[1 + 2 + 4 + 8 + \cdots + 2^{k} = \sum_{i=0}^{k} 2^i = 2^{k+1} - 1\]

• \(\sqrt{n} = n^{1/2}\)

• For any fixed logarithm base (such as \(\log_2\)), the following are true:

  • \(\log(xy) = \log x + \log y\)

  • \(\log x^y = y\log x\)

  • \(x^{\log y} = y^{\log x}\)