Department of Computer Science and Engineering, IIT Kanpur

CS210: Data Structures

Dr. R. K. Ghosh


Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources

Solution to Assignment 4

Tf=time to fetch
Ts=time to store
Tc=time to compare
To=time to perform a mathematical operation
Each line suggests the time taken for one line in the code given.
The total is assumed when each operation takes one unit of time.

1) a)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
sum++;
(2Tf+Ts+To)
total: 11N+7

b)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
for(j=0;j<N;j++)
{N(Tf+Ts)+N(N+1)(2Tf+Tc)+N*N(2Tf+Ts+To)}
sum+;
N*N(2Tf+Ts+To)
total: 11N2+12N+7

2) a)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
for(j=0;j<N*N;j++)
{N(Tf+Ts)+N(N2+1)(3Tf+Tc)+N3(3Tf+Ts+To)}
sum++;
N3(2Tf+Ts+To)
total: 13N3+13N+7

b)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
for)j=0;j<i;j++)
{N(Tf+Ts)+ΣN(2Tf+Tc)+Σ(N-1)(2Tf+Ts+To)}
sum++;
Σ(N-1)(2Tf+Ts+To)
total:11N2/2-21N/2+3

3) a)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
for(j=0;j<i*i;j++)
{N(Tf+Ts)+Σ(N2)(3Tf+Tc)+Σ(N2)(3Tf+Ts+To)}
for(k=0;k<j;k++)
{NΣN2(Tf+Ts)+ΣN(ΣN2+1)(2Tf+Tc)+Σ(N-1)Σ(N2)(2Tf+Ts+To)}
sum++;
Σ(N-1)Σ(N2)(2Tf+Ts+To)
total : 11N5/6+5N4/4+9N3/2-71N2/12+11

b)
sum=0;
(Tf+Ts)
for(i=0;i<N;i++)
{(Tf+Ts)+(N+1)(2Tf+Tc)+N(2Tf+Ts+To)}
for(j=0;j<i*i;j++)
{N(Tf+Ts)+Σ(N2)(3Tf+Tc)+Σ(N2)(3Tf+Ts+To)}
if(j%i==0)
ΣN2(2Tf+To+Tc)
for(k=0;k<j;k++)
{ΣNΣN2(Tf+Ts)+ΣNΣN(ΣN2+1)(2Tf+Tc)+ΣNΣ(N-1)Σ(N2)(2Tf+Ts+To)}
sum++;
ΣNΣ(N-1)Σ(N2)(2Tf+Ts+To)
total : 11N7/12+15N6/8+9N5/8+11N4/24+115N3/24+7N2+55N/6+47/4





Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Page last updated 20 Aug, 2002 by Manish Agarwal