CS2223 Algorithms 
Quiz 1 Solutions - B Term 2005

BY PROF. CAROLINA RUIZ 

Problem I. Asymptotic Growth Rates (50 points)

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))

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 n₀.]

   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 n₀.]

   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)

   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: 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). 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).