# 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 14th in class

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