A Guide to Time and Space Complexity in DSA

Welcome to the second part of the DSA learning series. If you haven't read the first part, I highly recommend giving it a read.

So, let's move on to today's topic. You might have guessed what we will discuss in this article.

Space and time complexity are easy to understand in theory, but they are crucial for a good grasp of DSA. In programming, everything boils down to how much time your program takes and how much extra space it requires.

In simpler terms, here's the definition for both:

Time complexity - This is the time your program takes to complete a task, based on the length of the input.

Space complexity - This is the extra space your program needs to complete a task, based on the length of the input.

From the above, you should understand what both terms mean. Let's explore this further.

There are basically three ways to measure complexity:

Big-O - Upper bound

Theta - Average bound

Omega - Lower bound

Among these, Big-O is the most commonly used, and we will discuss it in detail in this article.

There are 5 types of complexities in Big-O. Let's take a look at them:

1. Constant - O(1)

2. Linear - O(n)

3. Logarithmic - O(log n)

4. Quadratic - O(n^2)

5. Cubic - O(n^3)

Let’s discuss each of them one by one.

Certainly! Here's the expanded explanation with space complexity included for each type of time complexity:

Constant – O(1)

• Time Complexity: The time remains the same; the algorithm performs a set number of operations no matter how long the input is.

• Space Complexity: O(1) - The space required does not change with the input size.

• Example: Accessing a specific index; the input size does not change the cost.

• Code: x = arr[5]

Linear – O(n)

• Time Complexity: The time grows directly with input size; every element forces one unit of work.

• Space Complexity: O(1) - If no additional data structures are used, the space remains constant.

• Example: Scanning all elements to find a maximum value.

• Code:

    max_val = arr[0]
    for x in arr:
        if x > max_val: max_val = x
  

Logarithmic – O(log n)

• Time Complexity: The time grows according to how many times the input can be reduced by a fixed factor; each step operates on a smaller fragment.

• Space Complexity: O(1) - Typically, iterative logarithmic algorithms use constant space. Recursive versions may use O(log n) space due to the call stack.

• Example: Binary search repeatedly halving the search region.

• Code:

    while (low <= high):
        mid = (low + high) // 2
        if arr[mid] == target: return mid
        if arr[mid] < target: low = mid + 1
        else: high = mid - 1
  

Quadratic – O(n²)

• Time Complexity: Each element interacts with every other element; the workload forms a full cross-product as input grows.

• Space Complexity: O(1) - If no additional data structures are used, the space remains constant.

• Example: Checking all pairs to find duplicates.

• Code:

    for i in range(n):
        for j in range(i+1, n):
            if arr[i] == arr[j]:
                return True
  

Cubic – O(n³)

• Time Complexity: Each new element doubles the number of possible states the algorithm must evaluate.

• Space Complexity: O(1) - If no additional data structures are used, the space remains constant.

• Example: Generating all subsets of a set.

• Code:

    def subsets(nums):
        if not nums: return [[]]
        rest = subsets(nums[1:])
        return rest + [[nums[0]] + r for r in rest]
  

So far, we've learned about time and space complexity, how to measure them, and the different types of complexities.

When someone writes an algorithm, they usually start with linear complexity because it's the most straightforward; as your input grows, it takes more time and space. Our goal is to reach O(log n) because O(1) is very hard to achieve in a production codebase, though it might be possible in some scenarios.

In the next part, we will dive deeper and explore more topics in DSA.

Stay tuned for the next part and follow for more updates.