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 ]

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 n⁰]