WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS2223 Algorithms 
Quiz 1 Solutions - B Term 2005

BY PROF. CAROLINA RUIZ 

------------------------------------------

Problem I. Asymptotic Growth Rates (50 points)

The purpose of this problem is to prove the following property, called transpose symmetry, of the big-O and the big-Omega notations:
For any non-negative functions f(n) and g(n): f(n) is O(g(n)) if and only if g(n) is Ω(f(n))
We'll prove this result in two steps:
  1. (25 points) Let f(n) and g(n) be positive functions, Prove that if f(n) is O(g(n)) then g(n) is Ω(f(n)).

    [Remember that your proof must be general to any functions f(n) and g(n) that are positive. Also, remember to state and use the necessary constants c and n0.]

    Solution:

    If f(n) is O(g(n)) then
       there exist a constant c > 0, and a constant n0 such that for all n ≥ n0: f(n) ≤ c*g(n)

    hence:
       there exist a constant c > 0, and a constant n0 such that for all n ≥ n0: g(n) ≥ (1/c)*f(n)
         note that since c > 0, then the constant (1/c) > 0

    hence:
       there exist a constant k > 0, namely k = (1/c), and a constant n0 such that for all n ≥ n0: g(n) ≥ k*f(n)

    which is the definition of g(n) = Ω (f(n)).

  2. (25 points) Let f(n) and g(n) be positive functions, Prove that if g(n) is Ω(f(n)) then f(n) is O(g(n)).

    [Remember that your proof must be general to any functions f(n) and g(n) that are positive. Also, remember to state and use the necessary constants c and n0.]

    Solution:

    If g(n) = Ω (f(n)) then
        there exist a constant k > 0, and a constant n0 such that for all n ≥ n0: g(n) ≥ k*f(n)

    hence:
        there exist a constant k > 0, and a constant n0 such that for all n ≥ n0: f(n) ≤ (1/k)*g(n)
           note that since k > 0, then the constant (1/k) > 0

    hence:
        there exist a constant c > 0, namely c = (1/k), and a constant n0 such that for all n ≥ n0: f(n) ≤ c*g(n)

    which is the definition of f(n) = O(g(n)).


Problem II. Analysis of Algorithms(50 points)

Remember that the sequence of Fibonacci numbers is: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... In other words, if F(n) denotes the nth Fibonacci number, then F(0)= 0; F(1) = 1; and F(n) = F(n-2) + F(n-1).
Consider the following iterative algorithm that given n outputs the nth Fibonacci number, as discussed in class:
   function Fibiter(n) {
      if (n < 2) return n
      else {
         temp1 := 0
         temp2 := 1
         while (n > 1) {
            sum := temp1 + temp2
            temp1 := temp2
            temp2 := sum
            n := n-1
         }
      }
      return sum
   }

  1. (30 points) Analyze the runtime of the algorithm. That is, provide a function T(n) such that the algorithm will take T(n) steps to produce the output for input n. In the table below, show how much time each line will take and then multiply each line by the number of times it will be repeated (in case of the while loop).

    Instruction Time taken per instruction Number of repetitions Total time taken by instruction
    function Fibiter(n) {      
      if (n < 2) return n constant c1 1 c1
      else {      
        temp1:=0 constant c2 1 c2
        temp2:=1 constant c3 1 c3
        while (n > 1) { constant c4 n c4*n
          sum:=temp1+temp2 constant c5 n-1 c5*(n-1)
          temp1:=temp2 constant c6 n-1 c6*(n-1)
          temp2:=sum constant c7 n-1 c7*(n-1)
          n:=n-1 constant c8 n-1 c8*(n-1)
        }      
      }      
      return sum constant c9 1 c9
    }      

    We will concentrate here in T(n) when n ≥ 2 (hence in the proof below, we will use n0 ≥ 2):

    T(n) = c2 + c3 + c4*n + c5*(n-1) + c6*(n-1) + c7*(n-1) + c8*(n-1) + c9
      = [ c2 + c3 + c9 - c5 - c6 - c7 - c8 ] + [ c4 + c5 + c6 + c7 + c8 ] * n
      = k0 + (k1*n), where k0 and k1 are constants.

  2. (20 points) Provide a function g(n) such that your T(n) = Θ(g(n)). Prove in detail that T(n) = Θ(g(n)). That is, you need to show that T(n) = O(g(n)) AND that T(n) = Ω(g(n)).

    Solution:

    Claim: T(n) = Θ(n).
    Proof: As shown above T(n) = k0 + (k1*n), where k0 and k1 are constants, and n &ge 2. We show T(n) = Θ(n) in two steps:

    1. T(n) = O(n):

      Take constant c = (k0 + k1) &ge 0, and take n0 = 2. Then for all n &ge n0:
          T(n) = k0 + (k1*n) &le (k0*n) + (k1*n) = (k0 + k1)*n = c*n

      Hence T(n) = O(n).

    2. T(n) = Ω(n):

      Take constant a = k1 &ge 0, and take n0 = 2. Then for all n &ge n0:
          T(n) = k0 + (k1*n) &ge k1*n = a*n

      Hence T(n) = Ω(n).