Analysis of Nonrecursive Algorithms: Counting

We just count the number of basic operations.

Loops will become series sums

So we'll need some series formulas

Example: Maximum Element

Algorithm MaxElement( A[0...n-1] )

maxval ← A[0]

for i ← 1 to n-1 do

if A[i] > maxval then maxval ← A[i]

return maxval

What is the problem size? n

Most frequent operation? Comparison in the for loop

Depends on worst case or best case? No, has to go through the entire array

C(n) = number of comparisons

C(n) = ∑_i₌₁ⁿ^-1 1 = n-1 ε Θ(n)

Analysis Procedure

1. Decide on problem size specification

2. Identify basic operation

3. Check worst, best, average case

4. Count: set up the sum

5. Evaluate or determine order of sum

Series Rules and Formulas

Multiplication of a Series: ∑_i_=l^u ca_i = c∑_i_=l^u a_i

Sum of two sequences: ∑_i_=l^u (a_i + b_i) = ∑_i_=l^u a_i + ∑_i_=l^u b_i

Sum of constant sequences: ∑_i_=l^u 1 = u - l + 1

Sum of linear sequences: ∑_i₌₀ⁿ i = n(n+1)/2 = length of sequence times the average of the first and last elements

Example: Uniqueness

Progress through the sequence from 0 to n-2 checking the remainder with equality

Algorithm UniqueElements( A[0...n-1] )

for i ← 0 to n-2 do

for j ← i+1 to n-1 do

if A[i] = A[j] return false

return true

1. Problem size? n

2. Basic operation? if-test

3. Worst and best case are different. Best case is when the first two elements are equal then Θ(n)

Worst case is if array elements are unique then all sequences of the for loops are executed

4. The sum:

C_worst(n) = ∑_i₌₀ⁿ^-2∑_j_=i+1ⁿ^-1 1

5. Solove

C_worst(n) = ∑_i₌₀ⁿ^-2[(n-1) - (i+1) + 1] = ∑_i₌₀ⁿ^-2[n-1- i] = ∑_k_=n-1¹k where k = n - i -1

C_worst(n) = ∑_k₌₁ⁿ^-1k = (n-1)(n-1+1)/2 = n(n-1)/2 ε Θ(n²)

Note for a unique array there is minimal of n(n-1)/2 comparisons. Is this necessary, is there a better algorithm?

Yes we could pre-sort.

Another Example: Binary Length

The number of binary digits in a number.

Algorithm Binary(n)

count ← 1

while n > 1 do

count++

n ← floor(n/2)

return count

1. Problem size? integer, n

2. Basic operation? comparison in the while loop

3. Worst and best case are the same.

4. The sum:

How many times is the while loop executed?

approximately lg(n), exactly lg(n) + 1 because it must fail once

C(n) = ∑_i₌₁^lg(n)+1 1

5. Solve

C(n) = lg(n) +1 - 1 + 1 ε Θ(lg(n))