S1 9 Give using big oh notation the worst case running time

S1 #9 )

Give, using \"big oh\" notation, the worst case running times of the following procedures as a function of n greaterthanorequalto 0. procedure matzero for i = 1 to n do for j = 1 to n do begin C[i, j] leftarrow 0 for k = 1 to n do C[i, j] leftarrow C[i, j] + A[I, k]*B[k, j] endfor endfor endfor procedure unknown for i = 1 to n - 1 do for j = i + 1 to n do for k = 1 to j do {statements requiring Q(1) time} endfor endfor endfor procedure quiteodd for i = 1 to n do if odd(i) then for j = 1 to n do x leftarrow x + 1 endfor for j = 1 to i do y leftarrow y+1 endfor endif endfor function recursion (n) if n

Solution

Answer:

a) Here three for loops are there : one for loop runs from 1 to n ,therefore complexity = O(n)

second for loop runs from 1 to n , complexity = O(n)

Third for loop runs from k =1 to n , complexity = O(n)

Total complexity = O(n) * O(n) * O(n) = O(n^3)

c) The big O complexity is O(n^2)

d) The recurrence will be 2T(n -1) + 1

Solve by substitution,

T(n) = 2T(n -1) + 1

   = 2 [ 2T(n-2) + 1) ] + 1

   = 2^2 T( n - 1) + 2

:

:

T(n) = 2^kT(n -1) + kn

let n = 2^k => logn = k

T(n) = 2^logn T( n - n) + nlogn

= 0 + nlogn

=) T(n) = O(nlogn)