CS502 Fundamentals of Algorithms Assignment 1 Solution Spring 2013

Question: 1

Analyze the following pseudo code containing nested loops by computing its worst-case running time complexity. Perform all the steps by writing out the loops as summations and then solve the summations.

  1. for  i = 1    to   log n
  2. {          set   j = 1 ;       // ignore its constant time in analysis
  3.              while ( j <= i )
  4.              {         for  k = 1    to  j
  5.                          {         k=k+1;
  6.                          }
  7.             j  = j * 2 ;         // ignore its constant time in analysis
  8.            }
  9. }

[Note: Consider log as base 2 log and computing model  as RAM (Random Access Machine) like one used in lectures ]

 Solution:

For inner FOR loop
I(j)=Σ1=j
For middle WHILE loop
M(i)= ΣI(j)
=Σj
=i(i+1)/2
For outer FOR loop
T(n)= ΣM(i)
=Σ i(i+1)/2
=logn (logn+1)/2

 

Question: 2                            Marks: 10

 

Part (a)

 

What is the Asymptotic equivalence ( ) of the below function f(n)?

 

f(n) = 2n3 + 3n2 – 2n

 

Part (b)

Prove the Asymptotic equivalent of function in Part (a) by its lower and upper bounds.

[Note: You do not need to draw the graph, only show lower and upper bounds with c1,c2 and n0]

Solution:

F(n) = 2n^3 + 3n^2-2n
Lower Bound:
G(n^3)
For this we show that f(n) >=c1n^3 and n>=n0
F(n)= 2n^3 + 3n^2 – 2n >= 2n^3 -2n = n^3 +( n^3 -2n) >= n^3
n^3 is compare with c1n^3 so
c1 = 1
We implicitly assumed that 3n^2 >= 0 and n^3 – 2n >=0 These are
not true for all n . If n >=2 then it is true for both. We chek this by
putting values in 3n^2 >= 0 and n^3 – 2n >=0 .
Now n>=under root(2) so n0 >= 2 So f(n) >= C1n^3 for all n>=n0
Upper Bound:
F(n)= 2n^3 + 3n^2 – 2n <= 2n^3 + 3n^2 <= 2n^3 + 3n^3 = 5n^3
By compare 5n^3 with c2n^3 So c2 = 5
We implicitly made the assumption that 3n^2 <= 3n^3
It is true for all n >= 1 So n0 >= 1
From lower bound n0 >= under root(2)
Upper bound n0 >= 1
By combining both n0 >= underroot(2) , c1 = 1 , c2 = 5 so we
get asymptotic equivalence n^3 <= 2n^3 + 3n^2 – 2n <= 5n^3 for
all n >= under root(3)
So
0 <= C1g(n) <= f(n) <= C2g(n) for all n >= n0

DOWNLOAD SOLUTION HERE
loading...