IC312: Data Structures (FA16)


Home Policy Calendar Units Assignments Resources

HW 4: Big-O of Recursive Functions

Solution

You can find the solution here

Overview

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

Due Date

This homework is due Wednesday, September 13th in class

Grading

The assignment is graded out of 100 points. Each question is worth 10 points.

Submission and Starter Code

Submission must occur in hard copy at the start of class.

Problems

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.

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

Useful stuff to know

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