Topic- Time and Space Complexity
Subject Name/Code- Data Structure/IT 303
Department of IT
Complexity of an Algorithm
1. It is a function describing the efficiency of the algorithm.
2. The efficiency of an algorithm is mainly defined by two factors i.e. space and time.
3. A good algorithm is one that is taking less time and less space.
4. There is a trade-off between time and space.
B. Time Complexity
• The time complexity is the number of operations an algorithm performs to
complete its task with respect to input size
• The algorithm that performs the task in the smallest number of operations is
considered the most efficient one.
• It is represented by Big(oh) notation means maximum time taken by the
program.
Time Complexity (Example)
Main()
{
i=1;
for (i=1;i2<=n;i++) // i<=n1/2
{
printf(“ITM”)
}
}
Big Oh=> O(n1/2)
A. Space Complexity
• Space Complexity of an algorithm denotes the total space used or needed by the
algorithm for its working, for various input sizes.
• when you are creating a variable then you need some space for your algorithm to
run.
• All the space required for the algorithm is collectively called the Space
Complexity of the algorithm.
Space Complexity (Example): To find Extra space required by an Algorithm
Algorithm
1. Iterative 2. Recursive
1. Iterative:
Algo(A,1,n)
{
int i; or int i,j; = 1 or 2 or 3
for (i=1 to n)
A[i];
}
O(1) - Neglect input size
Space Complexity (Example):
Algo(A,1,n) - if input size is increase then extra space will increase.
{
int i; O(1)
create B[n]; O(n)
for (i=1 to n)
B[i]=A[i];
}
O(n+1)= O(n)
Recursive(Example):
A(n)
if (n>=1)
A(n-1);
Print(n);
A(n-1);
