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