DSA Time Complexity

What Is Time Complexity?

Time complexity describes how the runtime of an algorithm grows as the size of its input, usually called n, increases. Instead of measuring exact seconds — which depend on hardware, language, and even how busy the machine is — we count how the number of basic operations scales with n. This lets us compare algorithms independently of any particular computer.

Big O Notation

Big O notation describes the upper bound of an algorithm's growth rate in the worst case. Writing O(n) means the number of operations grows no faster than a constant multiple of n as n gets large. Big O ignores constant factors and lower-order terms because they become insignificant for large n — O(3n + 5) and O(n) describe the same growth rate.

• O(1) - constant time: the same number of steps regardless of input size
• O(log n) - logarithmic time: steps grow slowly as input size doubles
• O(n) - linear time: steps grow directly proportional to input size
• O(n log n) - linearithmic time: typical of efficient sorting algorithms
• O(n^2) - quadratic time: steps grow with the square of input size
• O(2^n) - exponential time: steps double with each additional input element

def get_first_element(items):
    # Accessing by index takes the same time
    # no matter how large the list is.
    return items[0]

numbers = [4, 8, 15, 16, 23, 42]
print(get_first_element(numbers))  # 4

def contains_value(items, target):
    # In the worst case every element must be
    # checked once, so time grows linearly.
    for item in items:
        if item == target:
            return True
    return False

numbers = [4, 8, 15, 16, 23, 42]
print(contains_value(numbers, 23))  # True

def binary_search(items, target):
    # Each step cuts the remaining search space in
    # half, so the work grows logarithmically.
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

sorted_numbers = [4, 8, 15, 16, 23, 42]
print(binary_search(sorted_numbers, 16))  # 3

Comparing Growth Rates