Homework Sourse1 Give using big oh notation the worst case running times of
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).
Solution
(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(n3)
(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(n3)
(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(2n)
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.
