This is the archived website of IC 312 from the Fall 2015 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 4: Big-O of Recursive Functions

  • Due before class on Wednesday, September 16

Remember to turn in a neat final draft of this homework.

Write the recurrence relations for the following algorithms. You do not need to find the Big-O of the relations.

  1. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    class Node {
  int data;
  Node next;
}
 
int niners(Node first) {
  return niners(first, 1);
}
 
int niners(Node cur, int x) {
  if (cur == null) {
    System.out.println("Pinker Cake");
    return x;
  }
  x += niners(cur.next, x);
  x += niners(cur.next, x);
  return x;
}
  2. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    void dolphins(int[] arr) {
  dolphins(arr, arr.length)
}
 
void dolphins(int[] arr, int end) {
  if (end == 0) {
    return
  }
  else {
    for (int i = 0; i < end; i++) {
      print "Lethal Inn"
    }
    dolphins(arr, end-1);
  }
}
  3. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    void steelers(int[] arr) {
  steelers(arr, 0, arr.length);
}
 
void steelers(int[] arr, int beg, int end) {
  if ((end-beg) == 1) {
    System.out.println("Other Girls Beer");
    return;
  }
  else {
    int mid = (end+beg)/2;
    steelers(arr, beg, mid);
    steelers(arr, mid, end);
  }
}

Find the Big-O of the following recurrence relations. Show your work, like we did in class. It may 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}\)