Time Complexity
at e
Analysis
geG
ed
Iterative Loops & Code
l
n ow
t e
Performance Analysis
a
G
Time Complexity - Time Complexity measures the amount of time an algorithm takes to Complete, based on the
number of operation performed.
Sum_Of_Numbers(int n)
{
int sum = 0;
d ge
{
wl
for(int i = 1; i <= n; i++)
sum = sum + i;
e
o
}
n
print(sum);
}
t e
Space Complexity : - Space Complexity refers to the total amount of memory an algorithm requires to execute
including:
a
G
● Memory for Input Data and variables - Space needed to store the input and and variables used.
e
● Data Structures :- Memory used by arrays, linked lists, Stacks, Jueves, trees, and graphs.
● Recursive Calls :- space for function Call Stats and local Variables in recursive functions
g
● Auxiliary storages :- Memory for temporary results. and intermediate Calculations.
Example : - Store n Elements in Array
l
Store_Array(int n)
ed
w
{
int arr[n]; // array of size n
o
for(int i = 1; i <= n; i++)
n
{
arr[i] = i;
}
}
t e
Loops Time Complexity Analysis
a
G
1. for(i = 1; i <= n; i++)
e
{
g
printf("Knowledge Gate");
d
}
l
2. for(i = n; i > 0; i--)
{
w e
o
printf("Knowledge Gate");
n
}
3. for(i = 1; i <= n; i = i + 3)
{
at e
G
printf("Knowledge Gate");
e
}
ed g
l
4. for(i = 1; i <= n; i = i + 10)
{
w
printf("Knowledge Gate");
o
}
n
5. for(i = n; i > 0; i = i - 3)
{
at e
G
printf("Knowledge Gate");
e
}
6. for(i = n; i > 0; i = i - 10)
{
ed g
l
printf("Knowledge Gate");
w
}
n o
7. for(i = 1; i <= n; i = i * 2)
{
at e
G
printf("Knowledge Gate");
e
}
8. for(i = 1; i <= n; i = i * 7)
{
ed g
l
printf("Knowledge Gate");
w
}
n o
9. for(i = n; i >= 1; i = i / 2)
{
at e
G
printf("Knowledge Gate");
e
}
10. for(i = n; i >= 1; i = i / 7)
{
ed g
l
printf("Knowledge Gate");
w
}
n o
2
11. for(i = 2; i <= n; i = i )
at e
G
{
e
printf("Knowledge Gate");
g
}
5
12. for(i = 5; i <= n; i = i )
{
l ed
w
printf("Knowledge Gate");
o
}
n
13. for(i = n; i >= 2; i = √i)
{
at e
G
printf("Knowledge Gate");
e
}
14. for(i = n; i >= 5; i = ⁵√i)
ed g
l
{
printf("Knowledge Gate");
w
}
n o
n
15. for(i = 1; i <= 5 ; i = i * 5)
at e
G
{
e
printf("Knowledge Gate");
g
}
l
n 5
16. for(i = 5; i <= 5 ; i = i )
{
ed
w
print("Knowledge Gate");
o
}
n
17. for(i = 1; i < n; i = i + (n/2))
{
at e
G
printf("Knowledge Gate");
e
}
18. for(i = n; i > 0; i = i - (n/2))
ed g
l
{
w
printf("Knowledge Gate");
}
n o
19. i = n;
while(i >= 1)
at e
G
{
e
printf("Knowledge Gate");
g
i = i / 2;
d
}
wl
20. for(i = 1; i2 <= n; i = i ++)
printf("Knowledge Gate"); e
o
}
n
t
Nested Loops
a e
Nested loop means a loop that is placed inside another loop.
G
Nested loops are classified into two categories:
e
1. Independent Nested Loops
g
2. Dependent Nested Loops
d
1. Independent Nested Loops
l e
An Independent Nested Loop is a nested loop in which the number of iterations executed by the inner
loop does not depend on the current value of the outer loop.
ow
The inner loop executes a fixed number of iterations for every iteration of the outer loop.
The loop boundaries of the inner loop are independent of the outer loop variable.
n
The total number of iterations is obtained by multiplying the iterations of all loops.
General Form
for(...)
at e
G
{
for(...)
e
{
g
// statements
d
}
e
}
wl
Complexity Analysis
o
If the outer loop executes times and the inner loop executes times for each outer iteration, then
n
When both loops execute n times,
1. for(i = 1; i <= n; i++)
{
at e
G
for(j = 1; j <= n; j = j * 2)
{
e
printf("Knowledge Gate");
g
}
d
}
l
2. for(i = 2; i <= n; i = i2)
{
w e
o
for(j = n; j > 0; j = j / 5)
n
{
printf("Knowledge Gate");
}
}
3. for(i = n; i >=10; i = 10√i)
{
at e
G
for(j = n; j >= 5; i = 2√j)
{
e
printf("Knowledge Gate");
g
}
d
}
l
4. for(i = 2; i <= n; i = i++)
{
w e
o
for(j = 5; j <= n; j = j5)
n
{
printf("Knowledge Gate");
}
}
5. for(i = 1; i <= n; i++)
{
at e
G
for(j = 1; j <= n2; j++)
{
e
for(k = 1; k <= n; k = k + (n/2))
g
{
d
printf("Knowledge Gate");
e
}
l
}
}
n ow
6. for(i = 1; i <= n2; i++)
{
at e
G
for(j = 1; j <= n; j = j * 2)
e
{
for(k = 1; k <= n3; k = k * 2)
g
{
d
printf("Knowledge Gate");
e
}
l
}
w
}
n o