A problem statement can be solved in many ways. For instance, if we have an array of n integer numbers which are sorted in ascending order. We want to check whether a particular integer i is present in the array.
This problem can be solved in two ways :
We can visit each array element and compare it with i - target value . If at any time we find the i, we can stop our search. In worst case, i can be the last element of the array and we would have done total n comparisons before we could find i. Other worst scenario is that i is not present in the array and we still do n comparisons and not find i. As the size of array i.e. n increases are comparisons also increase.This is basically, Linear Scan!
Second method, as we know the array is sorted in ascending order. We can find the middle element of the array. For array of size n , the middle element can be found at n/2 index. We can compare the middle element of the array with our target integer i. If i == middle array element. We can stop our search and we have performed 1 comparison.
Other two possible scenarios are :
middle array element < target integer OR middle array element > target integer
In the first case, we can continue searching in the array part starting from (n/2 + 1) index to (n-1) index
and similarly in second case, we can search in the first half of the array which is from 0 index to(n/2-1)
We can continue the above process until we narrow down to only one element or find our target integer.The number of comparisons we do in this method are far less than Linear scan in worst case.
For example: n = 16
we are dividing our problem space from n=16 to 8 to 4 to 2 to 1 in worst case when the target integer is not present in the array. The number of comparisons are around log(n) <<<< n (for Linear Scan)
As we saw above, a simple problem of searching an integer in an array can be solved using two different approaches. This approaches can be simply called as algorithms.
There needs to be a way to compare algorithms available to solve a problem statement. A quick answer would be to code up and check the time required to execute the two algorithms!
Very clever, but thinking closely makes us realize that time required to execute programs depends on a lot of factors like the machine configuration on which it is being executed, the programming language chosen etc.
There is a need to have a standard way of comparison which is not biased based on machine configurations or programming language. The answer to this : Time and Space Complexity!
Time Complexity
Time Complexity tells us how many times instructions are executed as function of input size.
What does this mean ??
Suppose we have a for loop as below:
//n is a variable taken from user
for(int i=1;i<=n;i++) {
System.out.println("hello world);
}The above instruction of printing “hello world” is executed for n times.
Value of n | Number of times println "hello world" executed |
2 | 2 |
5 | 5 |
10 | 10 |
100 | 100 |
As we can see from above table, the number of times instruction of printing is executed, is dependent on size of input .So the time complexity of the above code snippet is O(n)( pronounced as Big-O) i.e. Linear Time Complexity.
Consider below code:
//n is a variable taken from user
for(int i=1;i<=n;i++) //runs for n times
{
for(int j=1;j<=n;j++)//runs for n times
{
System.out.println("hello world);//runs for n*n times
}
}
The above instruction of printing “hello world” is executed for n*n times.
Value of n | Number of times println "hello world" executed |
2 | 4 |
5 | 25 |
10 | 100 |
100 | 10000 |
As we can see from above table, the number of times instruction of printing is executed, is dependent on size of input .So the time complexity of the above code snippet is O(n*n) = O(n^2) i.e. Quadratic Time Complexity
Lets consider below code:
//n is an integer taken from the user
for(int i=1;i<=5;i++) {
System.out.println(n);
}
How many times is n printed ?
Value of n | Number of times println command executed |
2 | 5 |
3 | 5 |
5 | 5 |
10 | 5 |
20 | 5 |
25 | 5 |
100 | 5 |
As, we can see the, the input size does not affect the number of times println is executed. The execution of println statement is constant 5 , for all different values of n.
Such cases where the number of times instructions are executed are independent of input size, are termed to have Constant time complexity denoted by O(1)
Order of magnitude of some famous complexities : O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
Space Complexity
Space Complexity is defined as the amount of space required to execute the program as a function of input size. Space Complexity has two main components:
Space required to store input
Auxiliary Space - this is the extra space required to execute the program other than input
Important Tip:
Space required to store primitive data types like int, long etc and variables are not considered in Space Complexity. This will be clear from below examples.
Let us consider below two examples :
Example 1
//n is a variable taken from user
for(int i=1;i<=n;i++) //runs for n times {
for(int j=1;j<=n;j++)//runs for n times {
System.out.println("hello world);//runs for n*n times
}
}
The space required to run the above code as function of input is constant space complexity denotes as O(1). As the space required to store integers i , j and n are not changing for different values of input n.Hence, not considered in space complexity.
Example 2
int n = size of array taken from user
int[] a = new int[n];
for(int i=0;i<n;i++)//runs for n times
{
System.out.println(a[i]);
}
The above code has Space complexity of O(n). Please look at the table below:
Value of n | Memory in bytes required to store the array. |
2 | 2 * 4 bytes = 8 bytes |
4 | 4 * 4 bytes = 16 bytes |
10 | 10 * 4 bytes = 40 bytes |
25 | 25 * 4 bytes = 100 bytes |
100 | 100 * 4 bytes = 400 bytes |
**Note: integer takes 4 bytes in JAVA
As we can see, the memory required to store the array , linearly increases as the input size increases. Hence, the space complexity is O(n)
Notations used to express Time and Space Complexity
Asymptotic Notations viz. O(), Ω(), and Θ() are used to describe Time and Space Complexity.
Best Case scenario complexity are described using Ω (Big-Omega)
Worst Case scenario complexity are described using O(Big-O)
Average Case scenario complexity are described using Θ(Big-Theta)
Comments