More Complexity Examples

Example 1

I = 1
P = 1
while (I < N) do
{
  P = P * I
  I = I + 1
}

T(n) = 2 + (N - I) * (1 + 1 + 1)
     = 2 + (N - 1) * (3)
     = O(2 + (3N - 3))
     = O(N)

Example 2

z = 1.0
t = a
k = n
while K > 0 do
{
  if odd(k) then
    z = z * t
  k = k/2
  if K <> 0 then
    t = t * t
}

O(1) == 3 assignments
O(1) == 4 statements

k = n, n/2, n/4, n/8, ....

stop m iterations

Example 3

for I = 1 to N - 1 do
  for J = N downto I + 1 do
    if A[J-1] > A[J] then        -- count as 3 assignments
      swap(A[J-1], a[J])

inner loop
O((n - i) * 1) = O(n-i)

outer loop

goto’s and Complexity

• use goto’s to jump out of loops
• assume goto’s never taken

Return to CIS 350 Index Page