Time Complexity
CSE231: Algorithms
Md. Ferdouse Ahmed Foysal
What is Time Complexity?
• The time complexity of an algorithm is defined as the amount of time taken by an
algorithm to run as a function of the length of the input. Note that the time to run is
a function of the length of the input and not the actual execution time of the
machine on which the algorithm is running on.
• Time taken != time complexity
Time Complexity CSE231: Algorithms 1
How is Time complexity computed?
We will consider the listed instructions as fundamental instructions to compute the
time complexity and will set the time complexity to O(1).
• Assignment Operations
• Comparison
• Arithmetic Operations
• Bitwise Operations
• Logical Operations
• Function call
• Returning a value
• Looking up the value of a particular element in an array
Time Complexity CSE231: Algorithms 2
Assignment operations
int a = 5, sum;
Sum = a;
Time Complexity CSE231: Algorithms 3
Comparison
if( a > b )
{
printf("A is greater than b");
}
while( a > 0 )
{
printf("%d",a--);
}
Time Complexity CSE231: Algorithms 4
Arithmetic Operations
a + 7;
y - z;
a * b;
a / b;
a % b;
Time Complexity CSE231: Algorithms 5
Bitwise Operations
a & b;
y | z;
Time Complexity CSE231: Algorithms 6
Logical Operations
a && b;
y || z;
! a;
Time Complexity CSE231: Algorithms 7
Function call
#include<stdio.h>
void sum(int a, int b)
{
int s;
s=a+b;
printf("%d",s);
}
int main()
{
int a=5,b=7,x;
sum(a,b);
Time Complexity CSE231: Algorithms 8
Returning a value
#include<stdio.h>
int sum(int a, int b)
{
int s;
s=a+b;
return s;
}
int main()
{
int a=5,b=7,x;
x=sum(a,b);
printf("%d",x);
Time Complexity CSE231: Algorithms 9
Looking up the value of a particular element in an array
x= arr[5];
Time Complexity CSE231: Algorithms 10
Constant Complexity
• If the function or method of the program takes negligible execution
time. Then that will be considered as constant complexity.
Time Complexity CSE231: Algorithms 11
Constant Complexity (Example)
#include<stdio.h>
void main()
{
int a,b,sum; Total Complexity = O(1) + O(1) + O(2) + O(1)
= O(5)
= O(1)
a = 5; O(1)
b = 7; O(1)
sum = a + b; O(1) + O(1) = O(2)
printf("%d",sum); O(1)
Time Complexity CSE231: Algorithms 12
Complexity of a simple loop
int i;
for(i = 1 ; i <= 5 ; ++i)
{ Total Complexity = O(1) + O(5 * 1) + O(5*2)
= O(16)
= O(1)
}
O(1) O(1) i=i+1
O(2)
Time Complexity CSE231: Algorithms 13
Linear Complexity
• It imposes a complexity of O(N). It encompasses the same number of
steps as that of the total number of elements to implement an
operation on N elements.
Time Complexity CSE231: Algorithms 14
Example of Linear Complexity
int i;
n
for(i = 1 ; i <= 5 ; ++i)
{ Total Complexity = O(1) + O(5 * 1) + O(5*2)
= O(16)
= O(1)
}
O(1) O(1) i=i+1
Total Complexity = O(1) + O(n * 1) + O(n * 2)
O(2) = O(1) + 0(n) + O(2n)
= O(n)
Time Complexity CSE231: Algorithms 15
Quadratic Complexity
• It imposes a complexity of O(n2). For N input data size, it undergoes the
order of N2 count of operations on N number of elements for solving a
given problem.
Time Complexity CSE231: Algorithms 16
Example of Quadratic Complexity
int n,i,j,count=0; n Count
scanf("%d",&n); 1 1
2 4
for(i = 1 ; i <= n ; ++i){ O(n)
3 9
for(j = 1 ; j <= n ; ++j){ O(n)
count++; 5 25
}
}
printf("%d",count); Total Complexity = O(1) + (O(n) * O(n)) + O(1)
= O(n2) + O(2)
= O(n2)
Time Complexity CSE231: Algorithms 17
Cubic Complexity
• It imposes a complexity of O(n3). For N input data size, it undergoes the
order of N3 count of operations on N number of elements for solving a
given problem.
Time Complexity CSE231: Algorithms 18
Example of Cubic Complexity
int n,i,j,k,count=0; n Count
scanf("%d",&n); 1 1
2 8
for(i = 1 ; i <= n ; ++i){ O(n)
3 27
for(j = 1 ; j <= n ; ++j){ O(n)
for(k = 1 ; k <= n ; ++k){ O(n) 5 125
count++;
}
} Total Complexity = O(1) + (O(n) * O(n) * O(n)) + O(1)
} = O(n3) + O(2)
printf("%d",count); = O(n3)
Time Complexity CSE231: Algorithms 19
Logarithmic Complexity
• It imposes a complexity of O(log(N)). It undergoes the execution of the
order of log(N) steps. To perform operations on N elements, it often
takes the logarithmic base as 2.
Time Complexity CSE231: Algorithms 20
Example of Logarithmic Complexity
int n,i,count=0; n Count Logn
scanf("%d",&n); 8 3 Log2(8)=3
16 4 Log2(16)=4
for(i = 1 ; i < n ; i = i*2){ O(logn)
32 5 Log2(32)=5
count++;
} 64 6 Log2(64)=6
printf("%d",count);
Total Complexity = O(1) + O(logn) + O(1)
= O(logn) + O(2)
= O(logn)
Time Complexity CSE231: Algorithms 21
Square Root Complexity
• It imposes a complexity of O(√n). It encompasses the same number of
steps as that of the total number of elements to implement an
operation on N elements.
Time Complexity CSE231: Algorithms 22
Example of Square Root Complexity
int n,i,count=0; n Count √n
scanf("%d",&n); 4 2 √(4)=2
9 3 √(9)=3
for(i = 1 ; i * i <= n ; i++){ O(√n)
16 4 √(16)=4
count++;
} 25 5 √25)=5
printf("%d",count);
Total Complexity = O(1) + O(√n) + O(1)
= O(√n) + O(2)
= O(√n)
Time Complexity CSE231: Algorithms 23
Factorial Complexity
• It imposes a complexity of O(n!). For N input data size, it executes the
order of N! steps on N elements to solve a given problem.
Time Complexity CSE231: Algorithms 24
Example Factorial Complexity
#include<bits/stdc++.h> n No of string n!
using namespace std;
void permute(char a[], int l, int r) O(n!) 3 6 3! = 6
{
if (l == r) 4 24 4! = 24
printf("%s\n",a); 5! = 120
5 120
else {
for (int i = l; i <= r; i++) { 6 720 6! = 720
swap(a[l], a[i]);
permute(a, l + 1, r);
swap(a[l], a[i]);
}
}
}
Total Complexity = O(n!)
int main()
{
char str[]="ABCD";
int n = strlen(str);
permute(str, 0, n - 1);
return 0;
}
Time Complexity CSE231: Algorithms 25
Exponential Complexity
• It imposes a complexity of O(2N), For N elements, it will execute the
order of the count of operations that is exponentially dependable on
the input data size.
Time Complexity CSE231: Algorithms 26
Example Exponential Complexity
int fibo(int n)
{
if(n<=1){
return n;
}
Total Complexity = O(2n)
return fibo(n-1)+ fibo(n-2); O(2n)
Time Complexity CSE231: Algorithms 27
Priority
O(1) < O(logn) < O(n) < o(nlogn) < O(n2) < O(n3) < O(2x) < O(n!)
Time Complexity CSE231: Algorithms 28
Lets Practice
int n,i,j,count=0;
scanf("%d",&n);
for(i = 1 ; i <= n ; ++i){ O(n)
for(j = 1 ; j < n ; j=j*2){ O(logn)
count++;
}
}
printf("%d",count); Total Complexity = O(1) + (O(n) * O(logn)) + O(1)
= O(nlogn) + O(2)
= O(nlogn)
Time Complexity CSE231: Algorithms 29
Lets Practice
int n,i,j,count=0;
scanf("%d",&n);
for(i = 1 ; i <= n ; ++i){ O(n)
for(j = 1 ; j < n ; j=j*2){ O(logn)
}
}
for(i = 1 ; i <= n ; ++i){ O(n)
}
Total Complexity = O(1) + (O(n) * O(logn)) + O(n)
= O(nlogn) + O(n) + O(1)
= O(nlogn)
Time Complexity CSE231: Algorithms 30
Thank You
