Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
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 optimize them to obtain a more efficient solution.
What is time complexity?
The amount of time that an algorithm takes to run based on the input size is known as time complexity.
Let us see some complex expressions and their meaning
Time complexity
Meaning
O(1)
Constant time
O(log n)
Logarithmic time complexity
O(n)
Linear time complexity
O(n x n)
Quadratic time complexity
O(n^4+n^2)
Polynomial-time complexity
O(2n)
Exponential time complexity
O(n!)
Factorial time complexity
Time and Space Complexity Questions and Answers:
Q1. What is the time complexity of the following code?
def fun(n,m):
for i in range(n):
print(i)
for i in range(m):
print(i)
You can also try this code with Online Python Compiler
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) <= … <= 2n-1 x T(n-(n-1))
Since T(1) is constant. T(n) has a upper bound of O(2n) 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(2n).
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/2k) + k.
Let us find the smallest integer k such that 2k >=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.
Thus the time and space complexity both are O(N).
Frequently Asked Questions:
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 the final value based on different inputs, we can get a relation between the input and output and thus guess the 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 optimize time and space?
Optimization 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 optimize time and space?
We can optimize 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.