Saturday 27 April 2013
Question: 1 marks : 10
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.
for i = 1 to log n
{ set j = 1 ; // ignore its constant time in analysis
while ( j <= i )
{ for k = 1 to j
{ k=k+1;
}
j = j * 2 ; // ignore its constant time in analysis
}
}
[Note: Consider log as base 2 log and computing model as RAM (Random Access Machine) like one used in lectures ]
Answer:
we analyze the running time of an algorithm that has many complex nested loops? The
answer is that we write out the loops as summations, and then try to solve the summations. Let I(),
M(), T() be the running times for (one full execution of) the inner loop, middle loop, and the entire
program. To convert the loops into summations, we work from the inside-out. Let’s consider one pass
through the innermost loop. The number of passes through the loop depends on j. It is executed for
k = j; j−1; j−2;:::;0, and the time spent inside the loop is a constant, so the total time is just j+ 1.
We could attempt to arrive at this more formally by expressing this as a summation:
I(j) =Xj
k=0
1 = j + 1
Why the “1”? Because the stuff inside this loop takes constant time to execute. Why did we count
up from 0 to j (and not down as the loop does?) The reason is that the mathematical notation for
summations always goes from low index to high, and since addition is commutative it does not matter
in which order we do the addition.
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.
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)
[Note: You do not need to draw the graph, only show lower and upper bounds with c1,c2 and n0]
