Question

Please explain what we mean by Time Complexity and Space Complexity. Please provide a short survey of Complexity classes.

Answer 1

Solution : i> Time Complexity :  Time complexity is the amount of time taken by an algorithm to run as a function of the length of the input. In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input.

Time complexity is typically expressed in the big - O notation because it will give us an upper limit of the execution time i.e. the execution time in the worst case.

For example, we have the algorithm:

int count = 0;
for (int i = 0; i < N; i++) 
   for (int j = 0; j < i; j++) 
        count++;

Lets see how many times count++ will run.

When i=0, it will run 0 times.
When i=1, it will run 1 times.
When i=2, it will run 2 times and so on.

So total number of times count++ will run is 0+1+2+...+(N−1)=N∗(N−1) / 2.

Hence time complexity will be O(N^2).

ii> Space Complexity : Space complexity is the amount of space or memory taken by an algorithm to run as a function of the length of the input.

For example, we have the algorithm:

int count = 0;
for (int i = 0; i < N; i++) 
    for (int j = 0; j < i; j++) 
        count++;

Here total number of inputs is N .

Hence space complexity will be O(N).