Time and Space Complexity

What is Space Complexity?

Space Complexity of an algorithm is the amount of memory it needs to run and compile the program. It specifies the amount of temporary storage required for running the algorithm.

Why Should we care about space complexity?

If the problem or the input is small then you will not probably notice it, but when the input is big, then you will realize how much of a role, space complexity plays in your program. If you have not managed the space complexity for your program, it will take up more memory or space and which will eventually lag the process of giving output or worse the system will show “out of memory ” error.

Two Components of Space Complexity

Space needed by algorithm consists of the two components:-

1. The Fixed Static Part.
2. The Variable Dynamic Part.

The Fixed Static Part

1. It is independent of characteristics like number of input/output.
2. This part include the instruction space(i.e. space or code)
3. Space for simple variables, space for constants, and fixed size component variables.
4. We usually denote this fixed static part by Cp.

The Variable Dynamic Part

1. This part consists of the space needed by component variables whose size is dependent on the particular problem instance at runtime i.e. space needed by reference variables, and the recursion stack space.
2. We usually denote the space for the dynamic part by Sp.

So we can deduce the space required by a program using the knowledge that we gain so far, which is that

S(p)=Cp + Sp

where S(p) is the total space required by a program.

Lets take an example to understand much better.

public class SpaceComplexity
{
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.println("Enter the three numbers");
int x=scan.nextInt();
int y=scan.nextInt();
int z=scan.nextInt();
int sum=scan.nextInt();
sum=x+y+z;
System.out.println("The sum is"+sum);
}
}

For the program there are no instance characteristics and the space needed by x, y, z and sum is independent of instance characteristics. The space for each integer variable is 4 bytes(Java).

We have 4 integer variables and space needed by x, y , z and are 4*4= 16 bytes.

S(p)=Cp + Sp
S(p)=16 + 0                    
S(p)=8
Note: Sp is 0 because there are no run time variables that are changing.

Time Complexity

Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.

Two Components of Time Complexity

Time required T(P) to run a program P also consists of two components

1. A Fixed Part :- The compile time which is independent of the problem instance ->c
2. A Variable Part :- The run-time which depends on the problem instance -> tp(instance)

So the total time required to run a program can be expressed as:-

T(P)= Cp+ tp(instance)

Three Types of Time Complexity

Best Case Time Complexity :- Efficiency of an algorithm for an input of size N for which the algorithm takes the smallest amount of time.

Average Case Complexity :- Average case is used when worst case and best case does not gives any necessary information about algorithm’s behavior, then the algorithm’s efficiency is calculated on Random input.

Worst Case Time Complexity :- Efficiency of an algorithm for an input of size N for which the algorithm takes the longest amount of time.

Lets take an example to know how much your algorithm can effect time complexity :-

Assume that there are two friends Ajay and Vijay, they were asked to write a program to check whether a given number is prime or not, and they both had a different approach which you can see below

Using System.currentTimeMillis() method to calculate the total time taken by a program to complete execution.

In the above example the program in the left side of the window is using a for loop from i=2 to i≤n-1 while the program in the right side of the window is using for loop from i=2 to i≤√n. But we don’t see that much of a time difference does we, so now lets take another input, but this time a little bigger integer than before.

Did you noticed that how much of a difference it makes, and this is a just a gist of the real world input, because in reality the inputs can be really big and if you do not optimize your code, it will take more of the precious CPU time.

Conclusion

By now i hope that you would have understood the importance of optimizing your code so that it will take less space and time and so that it can be efficient. Remember it is a essence of a programmer to be able to optimize the code to save space and time, and you never know that how much can changing even a line in you program can effect in a long run.So, that is it for this concept from my side. See ya on my another blog.