Time and Space Complexities
Performance of an Algorithm is measured in Time and Space complexity.
- Time Complexity : way of representing the amount of time needed by a program to run to the completion.
- Space Complexity : amount of memory space required by an algorithm during a course of its execution. It is required in situations when limited memory is available and for the multi user system.
- Time Complexity
- Constant Time O(1)
- Logarithmic time
- Linear Time O(n)
- Quadratic Time O(n2)
- Exponential time
- Best Case : when the minimum amount of input is given
- Worst Case : when the maximum amount of input is given.
During analyses of algorithm, mostly we will consider worst case scenarios only
Assigning values to variables or return statement or print statements takes constant time 1 unit represented in O(1) , it won't be dependent on length of array or any other .
int a = 5; // 1
for(int i=0;i<n;i++) //n + 1 (n times loop runs, 1 time checks condition and fails)
System.out.println(i); // 1
----------------------------------
Time Complexity :
f(n) = 1 + (n+1) +1
f(n) = n+3
f(n) = n
= O(n)
Rules of Time Complexity
- * Find the fastest growing term
- * Take out the coefficent
- Drop Constants
{
for() { ... } // O(n)
for() { ... } // O(n)
}
----------------------------------
Time Complexity :
= O(n) + O(n)
= O( ̶2̶n) //dropping constants,2 is deleted
= O(n)
= O(n)
- Drop non-dominate term / growing term
f(n) = O(n) + O(n²) // O(n²) is fast growing, O(n) is non dominate
= O(n²)
- Different inputs => Different variables (Nested Loops)
for ( int i =0;i<a;i++) //O(n)
{
for ( int j=0;j<b;j++) { } //O(n)
}
Time Complexity
f(n)= O(a * b) // O(length of arrray a * length of array b)
f(n) = O(n * n )
f(n) = O(n² )
Time Complexities in Order :
O(1) < O(log n) < O(n) O(n log n) < O(n²) < O(2ⁿ) < O(n!)