Homework 4: Big-O of Recursive Functions

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

• Due before class on Friday, September 12

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  algo1(int[] a) {     algo1(a, a.length)   }     algo1(int[] a, int end) {     if (end == 0)       return     for (int i = 0; i < end; i++)       print "A Caveman Lady"     algo1(a, end-1);   }
2.  1 2 3 4 5 6 7 8 9 10 11 12 13  algo2(int[] a) {     algo2(a, 0, a.length);   }     algo2(int[] a, int beg, int end) {     if ((end-beg) == 1) {       print "Pain Salon"       return     }     int mid = (end+beg)/2;     algo2(a, beg, mid);     algo2(a, mid, end);   }
3.  1 2 3 4 5 6 7 8 9 10 11 12  algo3(int[] a) {     algo3(a, a.length);   }     algo3(int[] a, int end) {     if (end == 0) {       print "Ran Madly"       return;     }     algo3(a, end - 1);     algo3(a, end - 1);   }

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} 1,& n\le 5 \\ 3 + T(n-1),& n \ge 6 \end{cases}$$
2. $$T(n) = \begin{cases} 5,& n=0 \\ 7,& n=1 \\ 4 + T(n-2),& n\ge 2 \end{cases}$$
3. $$T(n) = \begin{cases} 3,& n\le 1\\ 1 + 2 T(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}$$