Recurrence Relation Homework, due Friday, 9/7

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

Write the recurrence relations for the following algorithms: (2 points apiece)

  1.   algo1(int[] a) {
    algo1(a,a.length)
  }

  algo1(int[] a, int end) {
    if (end == 0)
      return
    for (int i = 0; i < end; i++)
      print "I am seated in an office, surrounded by heads and bodies."
    algo1(a, end-1);
  }
  
  2.   algo2(int[] a) {
    algo2(a, 0, a.length);
  }

  algo2(int[] a, int beg, int end) {
    if ((end-beg) == 1) {
      print "The expression \'Breakfast of Champions\' is a registered
      trademark of General Mills, Inc., for use on a breakfast cereal
      product."
      return
    }
    int mid = beg + (end-beg)/2;
    algo2(a, beg, mid);
    algo2(a, mid, end);
  }
  
  3.   algo3(int[] a) {
    algo3(a, a.length);
  }

  algo3(int[] a, int end) {
    if (end == 0) {
      print "\'To be born again,\' sang Gibreel Farishta tumbling from the
      heavens, \'first you must die.\'"
      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. 3 pts apiece.

  1. \(T(5)=O(1)\)
    \(T(n) = O(1) + T(n-1)\)

  2. \(T(0)=O(1)\)
    \(T(1)=O(1)\)
    \(T(n) = O(1) + T(n-2)\)

  3. \(T(1)=O(1)\)
    \(T(n) = O(1) + 2*T(n/2)\)

  4. \(T(0)=O(1)\)
    \(T(n) = O(1) + 2*T(n-1)\)