DSA — Complexity

What is Complexity?

Complexity measures how an algorithm's resource usage grows with input size.

Time Complexity

How execution time grows with input size.

# O(1) - Constant
def get_first(arr):
    return arr[0]

# O(n) - Linear
def find_element(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# O(n²) - Quadratic
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Space Complexity

How memory usage grows with input size.

# O(1) space
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) space
def create_copy(arr):
    return arr.copy()

Common Complexities

Complexity	Name	Example
O(1)	Constant	Array access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort
O(2^n)	Exponential	Fibonacci (naive)

Mini Practice

1. Analyze time complexity of functions
2. Identify space complexity
3. Compare different algorithms
4. Optimize inefficient code

Up Next

Continue with Big O — Big O notation.