CS502-Fall2011
ASSIGNMENT1
Deadline
Your assignment must be uploaded/submitted at or before 1st November 2011.
Uploading instructions
Please view the assignment submission process document provided to you by
the Virtual University to upload the assignment.
Rules for Marking
It should be clear that your assignment will not get any credit if:
oThe assignment is submitted after due date.
oThe submitted assignment does not compile or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the concepts of Asymptotic Growth, making
analysis of pseudo code, recurrence relation development, asymptotic function
understanding and iterative solutions for recurrences.
Guidelines
RULES FOR CALCULATING TIME COMPLEXITY AND BIG-OH
Rule 00
Normally these formulas are very handy:
If x y = z then y z x = log
Also,
( )
2 1
1
n
n
i
i a a n a + = Σ=
( 1)
1 2
+ = Σ=
i n n
n
i
r
r r
m m
k
k
−
−
=
+
= Σ
1
1 1
0
( for n 1)
6
( 1)(2 1)
1
2 >=
+ +
= Σ=
i n n n
n
i
Rule 0
The condition that stops a loop executes ONE MORE time than the loop itself
(the last time is when it is evaluated false)
Rule 1
for (i=0;i
Rule 3
for (i=1;i
greater growth rate then f2(x). For example f1(x)=x5 and f2(x)= x6 it is obvious that f1(x)
has greater growth rate ( 26 > 25).This concept relate to complexity of algorithm ,an
algorithm having greater growth rate function means the algorithm has greater
complexity here f2(x) is more complex then f1(x).
Estimated Time 2.5 hour
For all parts of the question to understand maximum time is 1.25 hours and for
solution maximum time is 1.25 hour. It all depends upon your sheer
concentration.
Question (4*5)
Write piece of pseudo codes having the following time
complexities:
a) T1 (n) =n+
0
n
i
i
= Σ
b) T2 (n) =6n (log12n) +1+ (m/7) log (m)
c) O (z+m)
d) T3 (n) =
1
5 (1/)
n
i
n i
= Σ
Note: Where the base of “log “has not been mentioned take it as base “2”.
Solution will be upload soon
