Algorithm Analysis

Program Analysis

2.1. What value is returned by the following function? Express your answer as a function of [math]\displaystyle{ n }[/math]. Give the worst-case running time using the Big Oh notation.

  mystery(n)
      r:=0
      for i:=1 to n-1 do
          for j:=i+1 to n do
              for k:=1 to j do
                  r:=r+1
       return(r)

Solution

2.2. What value is returned by the following function? Express your answer as a function of [math]\displaystyle{ n }[/math]. Give the worst-case running time using Big Oh notation.

   pesky(n)
       r:=0
       for i:=1 to n do
           for j:=1 to i do
               for k:=j to i+j do
                   r:=r+1
       return(r)

2.3. What value is returned by the following function? Express your answer as a function of [math]\displaystyle{ n }[/math]. Give the worst-case running time using Big Oh notation.

   prestiferous(n)
       r:=0
       for i:=1 to n do
           for j:=1 to i do
               for k:=j to i+j do
                   for l:=1 to i+j-k do
                       r:=r+1
       return(r)

Solution

2.4. What value is returned by the following function? Express your answer as a function of [math]\displaystyle{ n }[/math]. Give the worst-case running time using Big Oh notation.

  conundrum([math]\displaystyle{ n }[/math])
      [math]\displaystyle{ r:=0 }[/math]
      for [math]\displaystyle{ i:=1 }[/math] to [math]\displaystyle{ n }[/math] do
      for [math]\displaystyle{ j:=i+1 }[/math] to [math]\displaystyle{ n }[/math] do
      for [math]\displaystyle{ k:=i+j-1 }[/math] to [math]\displaystyle{ n }[/math] do
      [math]\displaystyle{ r:=r+1 }[/math]
      return(r)

2.5. Consider the following algorithm: (the print operation prints a single asterisk; the operation [math]\displaystyle{ x = 2x }[/math] doubles the value of the variable [math]\displaystyle{ x }[/math]).

   for [math]\displaystyle{  k = 1 }[/math] to [math]\displaystyle{ n }[/math]
       [math]\displaystyle{ x = k }[/math]
       while ([math]\displaystyle{ x \lt  n }[/math]):
          print '*'
          [math]\displaystyle{ x = 2x }[/math]

Let [math]\displaystyle{ f(n) }[/math] be the complexity of this algorithm (or equivalently the number of times * is printed). Proivde correct bounds for [math]\displaystyle{ O(f(n)) }[/math], and [math]\displaystyle{ /Theta(f(n)) }[/math], ideally converging on [math]\displaystyle{ \Theta(f(n)) }[/math].

2.6. Suppose the following algorithm is used to evaluate the polynomial

[math]\displaystyle{ p(x)=a_n x^n +a_{n-1} x^{n-1}+ \ldots + a_1 x +a_0 }[/math]

   [math]\displaystyle{ p:=a_0; }[/math]
   [math]\displaystyle{ xpower:=1; }[/math]
   for [math]\displaystyle{ i:=1 }[/math] to [math]\displaystyle{ n }[/math] do
   [math]\displaystyle{ xpower:=x*xpower; }[/math]
   [math]\displaystyle{ p:=p+a_i * xpower }[/math]

How many multiplications are done in the worst-case? How many additions?
How many multiplications are done on the average?
Can you improve this algorithm?

2.7. Prove that the following algorithm for computing the maximum value in an array [math]\displaystyle{ A[1..n] }[/math] is correct.

  max(A)
     [math]\displaystyle{ m:=A[1] }[/math]
     for [math]\displaystyle{ i:=2 }[/math] to n do
           if [math]\displaystyle{ A[i] \gt  m }[/math] then [math]\displaystyle{ m:=A[i] }[/math]
     return (m)

Solution

Big Oh

2.8. True or False?

Is [math]\displaystyle{ 2^{n+1} = O (2^n) }[/math]?
Is [math]\displaystyle{ 2^{2n} = O(2^n) }[/math]?

2.9. For each of the following pairs of functions, either [math]\displaystyle{ f(n ) }[/math] is in [math]\displaystyle{ O(g(n)) }[/math], [math]\displaystyle{ f(n) }[/math] is in [math]\displaystyle{ \Omega(g(n)) }[/math], or [math]\displaystyle{ f(n)=\Theta(g(n)) }[/math]. Determine which relationship is correct and briefly explain why.

[math]\displaystyle{ f(n)=\log n^2 }[/math]; [math]\displaystyle{ g(n)=\log n }[/math] + [math]\displaystyle{ 5 }[/math]
[math]\displaystyle{ f(n)=\sqrt n }[/math]; [math]\displaystyle{ g(n)=\log n^2 }[/math]
[math]\displaystyle{ f(n)=\log^2 n }[/math]; [math]\displaystyle{ g(n)=\log n }[/math]
[math]\displaystyle{ f(n)=n }[/math]; [math]\displaystyle{ g(n)=\log^2 n }[/math]
[math]\displaystyle{ f(n)=n \log n + n }[/math]; [math]\displaystyle{ g(n)=\log n }[/math]
[math]\displaystyle{ f(n)=10 }[/math]; [math]\displaystyle{ g(n)=\log 10 }[/math]
[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=10 n^2 }[/math]
[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=3^n }[/math]

Solution

2.10. For each of the following pairs of functions [math]\displaystyle{ f(n) }[/math] and [math]\displaystyle{ g(n) }[/math], determine whether [math]\displaystyle{ f(n) = O(g(n)) }[/math], [math]\displaystyle{ g(n) = O(f(n)) }[/math], or both.

[math]\displaystyle{ f(n) = (n^2 - n)/2 }[/math], [math]\displaystyle{ g(n) =6n }[/math]
[math]\displaystyle{ f(n) = n +2 \sqrt n }[/math], [math]\displaystyle{ g(n) = n^2 }[/math]
[math]\displaystyle{ f(n) = n \log n }[/math], [math]\displaystyle{ g(n) = n \sqrt n /2 }[/math]
[math]\displaystyle{ f(n) = n + \log n }[/math], [math]\displaystyle{ g(n) = \sqrt n }[/math]
[math]\displaystyle{ f(n) = 2(\log n)^2 }[/math], [math]\displaystyle{ g(n) = \log n + 1 }[/math]
[math]\displaystyle{ f(n) = 4n\log n + n }[/math], [math]\displaystyle{ g(n) = (n^2 - n)/2 }[/math]

2.11. For each of the following functions, which of the following asymptotic bounds hold for [math]\displaystyle{ f(n) = O(g(n)),\Theta(g(n)),\Omega(g(n)) }[/math]?

Solution

2.12. Prove that [math]\displaystyle{ n^3 - 3n^2-n+1 = \Theta(n^3) }[/math].

2.13. Prove that [math]\displaystyle{ n^2 = O(2^n) }[/math].

Solution

2.14. Prove or disprove: <math>\Theta(n^2) = \Theta(n^2+1)<\math>.

2.16

2.18