This article aims to familiarise you with the concept of time and space complexity. After reading this article, you will better understand time and space complexity along with various ways to optimise them to obtain a more efficient solution.

To brush up on your knowledge of the basic complexity, you can read the article Time and Space complexity on Coding Ninjas Studio.

Here the outer loop runs for N times. In the ith iteration, the inner loop runs for M times and hence the time complexity is O(M). As the loop runs for N times, the time complexity is N x M i.e. O(N x M)

Q5. What is the time complexity of the following code?

def fun(n):
for i in range(n):
print(pow(i,n))

You can also try this code with Online Python Compiler

This is because fib(i) will call fib(i-1) and fib(i-2). But the fib(i) isn’t stored. So when we calculate fib(i+1), it will call fib(i) and so it will be calculated repeatedly for a number of times.

Here, the recurrence relation is: T(n) = T(n-1) + T(n-2) <= 2 x T(n-1)

Thus T(n) <= 2 x T(n-1) <= 4 x T(n-2) <= … <= 2^{n-1} x T(n-(n-1))

Since T(1) is constant. T(n) has a upper bound of O(2^{n}) i.e. exponential time complexity.

Similarly we can find the lower bound by using T(n)= T(n-1) + T(n-2) >= 2 x T(n-2)

T(n) >= 2 x T(n-2) >= 4 x T(n-4) … >= 2^{(n-1)/2} x T(n- (n-1).

Thus the lower bound of T(n) is also exponential.

Thus the time complexity of fib(n) is exponentially increasing i.e. T(n) = O(2^{n}).

Ans: Time complexity: O(N), Space complexity: O(N)

Figure 3: Shows working of recursion function

Here the recursion will run for N times as the base case is N=0. The recursion will call itself as many times until the value of N becomes 0.

Thus N times calling results in O(N) time complexity and O(N) space complexity

Alternative method: Here we can see that the print statement gets executed for N times. This indicates that the recursion is called for N times thus time complexity is O(N) and space complexity is O(N).

Here we are using binary search on the array “arr” to search the element item. Here in each search half of the array is eliminated. Thus the time complexity can also be written as

T(N) = T(N/2) + 1.

Now T(N/2) = T(N/4) + 1 substituting it in the above equation we get T(N) = T(N/4) + 2.

Thus T(N) = T(N/2^{k}) + k.

Let us find the smallest integer k such that 2^{k} >=N, thus k >= log2(N). As k is integer k= ceil(log2(N))

Here the inner loop will be executed for a maximum of N times. The reason is that the j is incremented every time in the while loop. The condition in the while loop will be executed for 2 x N time because the outer for loop runs for N time and while loop runs for N times.

Thus the time complexity is O(N).

Q15. What are the time and space complexity for the following program?

maxa=50
dp=[-1 for i in range(maxa+1)]
def fib(n):
if dp[n]!=-1:
return dp[n]
if n<=1:
return n
dp[n]=fib(n-1)+fib(n-2)
return dp[n]
print(fib(maxa))

You can also try this code with Online Python Compiler

Here the dp array is used for memorization. So it stores the fib(n) after it was calculated. Thus in calculating fib(n), the dp[n-1] and dp[n-2] are already calculated, so fib(i) takes O(1) time after its last two numbers are calculated. So fib(i) = constant + fib(i-1). Thus time complexity is O(N).

We are making an array of size n. Similarly, the maximum depth of the recursion will be n.

1.Is time complexity always greater than or equal to space complexity?

Yes, because if we allocate space x, then the time complexity for allocating the space will be O(x). Also, due to other loops and conditions, the time complexity is always greater than or equal to space complexity.

2. How to find out time complexity in an alternative easy way?

The easy way to find out time complexity would be by adding counter+=1 in the innermost loop. Using final value based on different inputs, we can get a relation between the input and output and thus guess approximate time complexity.

3. How to measure the space taken by the array?

In python, we can get the space taken by an array using the sys.getsizeof() function. For example, the sys.getsizeof(arr) gives the memory used by object arr.

4. What is the need to optimise time and space?

Optimisation of time is essential in writing efficient programs. A merge sort on normal computers can beat bubble sort on supercomputers. Similarly, using large memory can also result in runtime errors. Thus the efficiency of programs plays a vital role. A good program is both time and space-efficient.

5. What are the ways to optimise time and space?

We can optimise time and space complexity by using better algorithms and proper data structures. Removing unnecessary arrays can save space. Similarly, data structures like HashMaps can be beneficial in searching an element.

Conclusion

Here, we learn about various programs' time and space complexity. You can also copy the programs and run them at your local machines for better understanding. You can also edit them at your convenience and check the output.