Blog: CS502 Assignment Solution 2 shared by Malik Shafiq Awan

Solution
Question 1:
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

Q No.2:

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

please do guide me if its wrong
regards
Malik Shafiq Awan (Prince of Soon Valley)