Vidyavardhini’s College of Engineering & Technology, Vasai

Department of Computer Engineering

Academic Year 2024-25

Time Complexity of Iterative Algorithm

Code Snippet Explanation Time

Complexity

for ( i = 1; i <= n; i ++ ) Initialization i=1 (1 time) O(n)

{ Condition i <= n ( n + 1 times )
​ printf(“Hello”) Increment/decrement i ++ ( n times )
} print(“Hello”) (n times)

for ( i = n; i >= 1; i -- ) Initialization i=1 (1 time) O(n)

{ Condition i >=1 ( n + 1 times )
​ printf(“Hello”) Increment/decrement i - - ( n times )
} print(“Hello”) (n times)

for ( i = 1; i <= n; i = i + 2 ) Initialization i=1 (1 time) O(n)

{ Condition i <= n (n - 2 times ) (note: n = 6,
​ printf(“Hello”) if n = 10 then this condition will be
} 𝑛
evaluated for ( 2 + 1) times)
𝑛
Increment/decrement i = i +2 ( 2
times )
𝑛
print(“Hello”) ( 2
times)

𝑛
i = i 土 k → k is constant. Time complexity can be O(n) . k = 2 then loop iterates for 2
times , k = 3
𝑛
loop iterates for 3
.

for ( i = 1; i <=100; i = i ++ ) Initialization i=1 (1 time) O(1)

{ Condition i <= 100 ( 101 times )
​ printf(“Hello”) Increment/decrement i ++ ( 100 times )
} print(“Hello”) (100 times)

for ( i = n; i <=n; i ++ ) Initialization i=n (1 time) O(1)

{ Condition i <= n ( 2 time )
​ printf(“Hello”) Increment/decrement i ++ ( 1 time )
} print(“Hello”) (1 times)
Swap ( int x , int y ) int temp = x ( 1 time) O(1)
{ x = y ( 1 time )
​ int temp = x; y = temp ( 1 time )
x = y;
y = temp;
}

for ( i = 1; i < n; i = i * 2 ) Start: i = 1 O(log n)

{ Each time, i becomes double → i = i * 2
​ printf(“Hello”) So values of i will be: 1, 2, 4, 8, 16, ... until
} i < n. This continues as long as i is less
than n.

Think of the last value before i becomes

equal to or more than n.

𝑘
Let’s say after k times: (𝑖 = 2 ) < 𝑛 or
𝑘
(𝑖 = 2 ) = 𝑛

i = i * 2 increments are always in terms of

2k.
𝑘
2 =n
K = log2n
The loop doubles i each time, so it runs
logarithmically, not linearly.

for ( i = n; i > 1; i = i/2 ) Start: i = n O(log n)

{ Each time, you divide i by 2 → i = i / 2
​ printf(“Hello”)
So values of i will be: n, n/2, n/4, n/8, ...,
}
until i becomes ≤ 1.

You're dividing n by 2 every time. Let’s say

after k times:

𝑛 𝑘
𝑘 ≤ 1⇒2 ≥ 𝑛 ⇒ 𝑘 ≥ log2n
2

So it runs approximately log₂(n) times.

𝑖
i= 2
decrements are always in terms of 2k.
2k = n
 k = log2n
The loop divides i by 2 each time, so it
runs logarithmically, just like the previous
loop.

i = i * k & i = i / k → k is constant. Time complexity can be O(log k n) . k = O(log 2 n) , k = 3 O(log 3

n).

Nested loops

for ( i = 1; i <= n; i + + ) Outer loop - (n times) n * n = O(n2)

{ Inner loop - (n times)
for ( j = 1; j <= n; j + + )
For every value of ‘i’ , ‘j’ is
{
running ‘n’ times.
​ printf(“Hello”); n + n + n + ……….. + n
} i = 1 → j = n times n * n = O(n2)
} i = 2 → j = n times
i = 3 → j = n time
i = n → j = n time

for ( i = 1; i <= n; i + + ) For every value of ‘i’ , ‘j’ is 1 + 2 + 3 + ……….. + n =

{ running ‘i’ times. 𝑛(𝑛+1)
2
(𝑛 +𝑛)
2
= 2
= O(n2)
for ( j = 1; j <= i; j + + )
i = 1 → j = 1 time
{
i = 2 → j = 2 times
​ printf(“Hello”); i = 3 → j = 3 times
} i = n → j = n time
}

Consecutive Loops

for ( i = 1; i <= n; i + + ) First loop - ( n times) n + n = 2n

{ O(n)
printf(“Hello”); Second loop - (n times)
}
for (i = 1; i <= n; i + + )
{
​ printf(“Hello”);
}
for ( i = 1; i <= n; i + + ) First loop - (n times) n + n2 = O(n2)
{
printf(“Hello”);
}
Second loop
for (i = 1; i <= n; i + + ) Outer loop - (n times)
{ Inner loop - (n times)
for(j=1; j<=n; j++)
{ n * n = n2
​ printf(“Hello”);
}
}

for ( i = 1; i <= n; i + + ) First loop - (n times) n + n3= O(n3)

{
printf(“Hello”);
}
Second loop
for (i = 1; i <= n; i + + ) Outer loop - (n times)
{ Inner loop - (n times)
for(j=1; j<=n; j++) Inner loop - (n times)
{
for(k=1; k<=n; k++) n * n * n = n3
{
​ printf(“Hello”);
}
}
}

for (i = 1; i <= n; i + + ) i = 1 → j = n time n+

𝑛
+
𝑛
+
𝑛
+
2 3 4
{ i = 2 → j = n/2 times
i = 3 → j = n/3 times ………….+ 1
for(j=1; j<=n; j = j+i) n(1 + ½ + ⅓ + ¼ +...............+
i = n → j = n/n (only 1 time)
{ 1
)
𝑛
printf(“Hello”);
O(n log n)
}
}
int unknown(int n) i j Total no. of operations:
{ 1 + 2 + 3 + ………..+ n-1
int count = 0; 0 0 time =
2
𝑛(𝑛+1) (𝑛 +𝑛)
for(i = 0; i< n; i++) = = O(n2)
1 1 time 2 2
{
for(j = i; j > 0; j - -) 2 2 times(2,1)
{
count = count + 1; 3 3 times(3,2,1)
} n-1 n - 1 times
}
return count;
}

int unknown(int n) Outer loop: i → n,

𝑛
,
𝑛
,… n+
𝑛
+
𝑛
+ ………….+ 1
2 4 2 4
{ O(n)
int count = 0;
Inner loop: runs 'i' times
for (i = n; i > 0; i = i / 2)
{
for (j = 0; j < i; j++) i j
{
n n times
count = count + 1;
} 𝑛 𝑛
times
2 2
}
return count; 𝑛 𝑛
times
4 4
}
𝑛 1 time
𝑛

int unknown(int n) Outer loop: i → n,

𝑛
,
𝑛
,… (log n) * (log n) = O (log n)2
2 4
{
(log n) times
int count = 0;
for (i = n; i > 0; i = i / 2)
Inner loop: every time i →1 ,
{
2, 4, 6, 8, …………… n.
for (j = 0; j < = n; j = j * 2)
(log n) times
{
count = count + 1;
}
}
 return count; i j
}
n 1, 2, 4, …… n
𝑛 1, 2, 4, …… n
2

𝑛 1, 2, 4, …… n
4

𝑛 1, 2, 4, …… n
𝑛