FALLSEM2025-26_VL_BCSE202L_00100_TH_2025-07-23_Iterative-Algorithms.ppt

iterative

1. Iterative Algorithms
Running Time Analysis

2. •Algorithm types:
Iterative algorithms
Recursive Algorithms
Running time f(n) of non iterative and non
recursive algorithms is always constant. Hence
f(n) = O(1)

3. •Fn()
{
int i
for( i = 1 to n)
print(“VIT”)
}
Running Time : O(n)

4. •Fn()
{
int i,j
for(i = 1 to n) n times
for(j= 1 to n) n times
print(“VIT”)
}
Running time f(n) = O (n
2
)

5. •Fn()
{
i=1 s=1
while(s<=n)
{
i++
s=s+i
print(“VIT”)
}
}

s 1 3 6 10 15………n
where n =k(k+1)/2
i 1 2 3 4 5 ……….k
kth iteration s>n iteration
stops
k(k+1)/2 >n
k(k+1)/2>=n
k
2
= n
k = n
½
Running time = O(n
½
)

6. •Fn()
{
i=1
for(i=1; i
2
<=n;i++)
print (“VIT”)
}
•i = n
2
Running time = O(n
½
)

7. •Fn()
{
int i,j,k,n
for(i=1;i<=n;i++)
{
for(j=1;j<=i; j++)
{
for(k=1;k<=100;k++)
{
print(“VIT”)
} } } }
•i=1 j= 1 time k=1 *100 times
•i=2 j = 2 times k = 2 * 100times
•.
•.
•.
•i=n j=n times k = n *100 times
=100+200+300+….n*100
=100[1+2+3+……….+n]
=100* [(n(n+1))/2]
Running time = O(n
2
)

8. •Fn()
{
int i,j,k,n
for(i=1;i<=n;i++) n times
{
for(j=1;j<=i
2

;
j++) depends on i
{
for(k=1;k<=n/2;k++)
{
print(“VIT”)
}
}
}
}


•i=1 j=1 time k=1*n/2
•i=2 j=4 times k=4 *n/2
.
.
.
=n/2[1+4+9+………+n
2
]
=n/2 * [n(n+1)(2n+1)/6]
Running Time : O (n
4
)

9. •Fn()
{
for(i=1;i<n;i=i*2)
print (“VIT”)
}
i=1
i=2
i=4
i=8
2^0 2^1 2^2….2^k >=n
2^k =n
K= log n
Running time = O(log
2n)

10. •Fn()
{
int i,j,k
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)
log
2n times
print (“VIT”)
}
•n/2 * n/2 * log
2
n
Running time = O(n
2
log
2n )

11. •Fn()
{
int i,j,k
for(i=n/2;i<=n;i++)
for(j=1;j<=n;j=2*j)
for(k=1;k<=n;k=k*2)
Print(“VIT”)
}