Analyze the time complexity of below function
Q1)
A()
{
i=1;
s=1;
while(s<=n)
{
i++;
s=s+i;
print "hi"
}
}
for n=15 the values of i and s inside while loop as shown below:
i 1 2 3 4 5
s 1 3 6 10 15
for n=15, the while loop runs 5 times ..i.e, approximately sqrt(n) times
so time complexity = O(sqrt(n))
In depth explanation:
Let this while loop runs k times and after k iterations,
s would be sum of first k natural numbers.
and s must be >= n to come out of the loop
(k*(k+1))/2 = n
k*k+k >2*n
k*k approximately equal to n
k is approximately equal to sqrt(n)
===========================================
Analyze the time complexity of below function
Q2)
A()
{
i=1;
for(i=1;i*i <=n;i++)
{
print "hi"
}
time complexity = O(sqrt(n))
===========================================
Analyze the time complexity of below function
Q3)
A()
{
int i,j,k,n;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
for(k=1;k<=100;k++)
print "hi"
}
}
}
|i=1 |i=2 |i=3
j loop runs |1 time |1,2 that is 2 times |1,2,3 that is 3 times
for each j k runs |100 times |2*100 times |k=3*100
= 100+2*100+3*100 +.....+n*100
= 100*(1+2+3+............+n)
= O(n*n)
==============================================================
Q4)
A()
{
int i,j,k,n;
for(i=1;i<=n;i++)
{
for(j=1;j<=i*i;j++)
{
for(k=1;k<=n/2;k++)
print "hi"
}
}
}
|i=1 |i=2 |i=3 ..........n
j loop runs |1 time |1,2,3,4 i.e, 4 times |3*3=9 times......n*n
for each j k runs |n/2 times |4*n/2 times |9*n/2........(n*n)* n/2
= n/2+4*(n/2)+9*(n/2) +.....+(n*n)* (n/2)
= n/2*(1+4+9+............+n*n)
= n/2*(n*(n+1)*(2*n+1))/6
= O(n*n*n*n)
====================================================================
Q5)
for(i=1;i<n;i=i*2)
{
print "hi"
}
i will take values 1,2,4....n
2^0, 2^1, 2^2.....2^k
2^k =n and k=log2(n)
===================================================================
Q6)
while(n>1)
{
n = n/2
}
if n=16 then 16,8,4,2..4 times ...log2(16) = log2(n) times
======================================================================
Q7)
for(i=n/2;i<=n;i++) ........................n/2 times
{
for(j=1;j<=n/2;j++) .............. n/2 times
{
for(k=1;k<=n;k = k*2) ....... log2(n) times
print "hi"
}
}
= (n/2)*(n/2)*log2(n) = n*nlog2(n)
===========================================================================
Q8)
for(i=n/2;i<=n;i++) ........................n/2 times
{
for(j=1;j<=n;j = 2*j) .............. log2(n) times
{
for(k=1;k<=n;k = k*2) ....... log2(n) times
print "hi"
}
}
= (n/2)*log2(n)*log2(n) = n*log2(n)*log2(n)
