Time Complexity in Python: Linear and Quadratic

Understanding time complexity is crucial when writing efficient Python code. Time complexity helps you estimate the time an algorithm takes to complete as a function of its input size. In this blog, we will focus on two common time complexities: Linear (O(n)) and Quadratic (O(n²)).

Linear Time Complexity (O(n))

Linear time complexity means that the time taken by an algorithm increases proportionally with the size of the input. If you double the input size, the execution time also doubles. This is often seen in algorithms that involve single loops.

For example, iterating over a list:

def linear_search(arr, target):

    for i in range(len(arr)):

        if arr[i] == target:

            return i

    return -1

In this linear_search function, if there are n elements in the list, the function may need to look at all of them in the worst case (when the target is the last element or not present). Thus, the time complexity is O(n).

Quadratic Time Complexity (O(n²))

Quadratic time complexity means that the execution time increases as the square of the input size. This happens in algorithms with nested loops, where for each iteration of the outer loop, the inner loop runs through the entire input again.

Here's an example using a bubble sort algorithm:

def bubble_sort(arr):

    n = len(arr)

    for i in range(n):

        for j in range(0, n-i-1):

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

In the bubble_sort function, we have two loops. For each iteration of the outer loop, the inner loop runs fewer times but still depends on the input size n. Hence, the time complexity is O(n²), making it inefficient for large inputs.

Conclusion

When writing Python code, being aware of time complexity helps you choose the most efficient algorithm. For small datasets, the difference between O(n) and O(n²) may not seem significant, but as the size of the input grows, the impact becomes dramatic. Understanding this can help you optimize your code and save computation time.