Question

1. Give, using “big oh” notation, the worst case running times of the following procedures as a function of n ≥ 0.

(a). procedure unknown

for i =1 to n – 1 do

for j =i + 1 to n do

for k =1 to j do

{statements requiring O(1) time}

endfor

endfor

endfor

(b). procedure quiteodd

for i =1 to n do

if odd(i) then

for j =i to n do

x ← x + 1

                           endfor

                           for j =1 to i do

                                        y ← y + 1

                           endfor

             endif

endfor

(c). function recursion (n)

if n <= 1 then

return (1)

else

return (recursion (n – 1) + recursion (n – 1))

endif

2.

The function max (i, n) given below returns the largest element in positions i through i + n – 1 of an integer array A. Assume for convenience that n is a power of 2.

function max(i, n)

if n = 1 then

             return (A[i])

else

             m1 ← max (i, n/2)

             m2 ← max (i + n/2, n/2)

if m1 < m2 then

return (m2)

else

             return (m1)

endif

             endif

(a). Let T(n) denote the worst-case time taken by max with the second argument n. Note that n is the number of elements of which the largest is to be determined. Write an equation expressing T(n) in terms of T(j) for j < n and constants that represent the times taken by statements of the program.

(b). Obtain a big theta bound on T(n).  

Answer 1

(a). procedure unknown

for i =1 to  n – 1 do =========> Runs for max n times

for j =i + 1 to n do =========> Runs for max (n-1)*n times n-1 because of ouer loop

for k =1 to j do=========> Runs for max (n-1)*(n-1)*n times n-1 because of outer loop

{statements requiring O(1) time}-Runs for max (n-1)*(n-1)*(n-1) times n-1 because of outer loop

endfor

endfor

endfor

So overall time complexity is O(n³)

(b). procedure quiteodd

for i =1 to n do=========> Runs for max n+1 times, addition one for failure case

if odd(i) then=========> Runs for max n times because of outer for loop

for j =i to n do=========> Runs for max n*(n+1) times, n times because of outer for loop and max n times itself

x ← x + 1=========> Runs for max n*(n-1) times, n times because of outer for loop and max n -1 times itself

                           endfor

                           for j =1 to i do=========> Runs for max n+1*(n*n) times, n*n times because of outer fors loop and max n+1 times

                                        y ← y + 1=========> Runs for max n*(n*n) times, n*n times because of outer fors loop and max n times

                           endfor

             endif

endfor

So overall time complexity is O(n³)

(c). function recursion (n)

if n <= 1 then

return (1)

else

return (recursion (n – 1) + recursion (n – 1))

endif

Represents this in terms of recurrance relation
T(n) = 2T(n-1) + 1
If we solve it we will get T(n) = O(2ⁿ)



2)

function max(i, n)

if n = 1 then

             return (A[i])

else

             m1 ← max (i, n/2)

             m2 ← max (i + n/2, n/2)

if m1 < m2 then

return (m2)

else

             return (m1)

endif

             endif


This procedure is an example of divide and conquer:

It divides the problem into subrproblems of size n/2 twice

So if we write

T(N) = 2T(N/2) + 1

Solving using masters theorem we will get
T(N) = O(N) we can say theta N as well

Thanks, let me know if there is any concern.