Time and Space Complexity.
TIME COMPLEXITY
Definition:- Relation between input Size & Running time(Operations)
- time complexity is directly proportional to the input size.
Time complexity has three cases
- BEST CASE Ω(1)
- AVERAGE CASE Ө(n+1/2)
- WORST CASE O(n)
// In the nested loop time complexity is calculated by n*n; eg-2,3;
//In a nonnested loop time complexity is calculated by n+n; eg-4;
Ex:1
#include <stdio.h>
int main(void) {
int n;
printf("Enter a value");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
printf("hello");
}
return 0;
}
input n=5
time complexity n=n 5 = 5
Ex:2
#include <stdio.h>
int main(void) {
int n,val =0;
printf("Enter a value");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
val = val+j;
printf("%d\n",val);
}
}
return 0;
}
input n=5
time complexity n*n = 5*5 = 25
Ex:-3
#include <stdio.h>
int main(void) {
int n,m,val =0;
printf("Enter a value");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
val = val+j;
printf("%d\n",val);
}
}
return 0;
}
input n=5
input m=4
time complexity n*n = 5*4 = 20
Ex:-4
#include <stdio.h>
int main(void) {
int n,m;
printf("Enter a value");
scanf("%d", &n);
printf("Enter a value");
scanf("%d", &m);
for (int i = 0; i < n; i++) {
printf("Hello");
}
for (int j = 0; j < n; j++) {
printf("HEllo");
}
}
return 0;
}
input n=5
input m=4
time complexity n*n = 5+4 = 9
Eg:-
compare: O(n) O(n^2) O(n^3)
n=1 1 1 1
n=2 2 4 8
n=3 3 9 27
↓ --------------------------------------
n=10^8 | 105 | 10^10 | 10^30 |
--------------------------------------
You can clearly see a big difference here when you put exponential/large input.
Comparison of functions on the basis of time complexity
It follows the following order in case of time complexity:
O(nn) > O(n!) > O(n3) > O(n2) > O(n.log(n)) > O(n.log(log(n))) > O(n) > O(sqrt(n)) > O(log(n)) > O(1)
Note: Reverse is the order for better performance of a code with corresponding time complexity, i.e. a program with less time complexity is more efficient.
SPACE COMPLEXITY
Ex:1 //space is constant in this case
#include <stdio.h>
int main(void) {
int n;
printf("Enter a value");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
printf("hello");
}
return 0;
}
//here you can store printf and their string, n and int i, etc...
//You are exponentially increasing the value of n that doesn't affect this space complexity
Ex:2 //space isn't constant in this case
array
The space complexity of an algorithm quantifies the amount of time a program takes to run as a function of the length of the input. It is directly proportional to the largest memory your program acquires at any instance during run time.
For example: int consumes 4 bytes of memory.speed = distance/time
time = distance/speed
O(n)log^n
O(n^2)
O(n^3)
O(n!)
Comments