CS502 assignment no 2 spring 2011

[Real sweeto]

Question 1
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<n;i=i+k) Anything inside the loop will run approximately n/k times
Rule 2
for (i=n;i>0;i=i-k) Anything inside the loop will run approximately n/k times
Rule 3
for (i=1;i<n;i=i*k) Anything inside the loop will run approximately logkn times
Rule 4
for(i=1;i<=n;++i)
for (j=1;j<=i;++j)
The above nested loop approximately runs ½ n(n+1) times.
The variable j depends upon the value of i
Rule 5
for(i=1;i<=n;i=i*2)
for (j=1;j<=i;++j)
The statements in the above nested loop approximately run
2n-1 times.
The variable j depends upon the value of i
Rule 6
If the loop variables are independent then the total times a statement inside a
nested loop is executed is equal to the product of the times the individual loops
run
e.g. for (i=0;i<n;++i)
for (j=0;j<m;++j)
A statement inside the above nested loop will run n*m times

Question 2 (10)
Arrange the following in the Most to Least complexity order. Here “n “is the input size
for the some complexity function and k< j and j & k are numbers greater than 2.Every
function is separated by “comma” and note these are 20 functions to arrange.
2
2 4 8
5 6
n, n / 2, n j/2, nlgn, nn, 1,100, 2n, lgn, n!,(n! ) / ,
/ ,n! log / , / log ,10000,n / , (log ) ,
n / , (log ) ,1000
k n n n
n n n n n n n nn n n
n n n n


plz check and if corection is required then tell me. thanks
(Remember in prayers)