What Is an Algorithm? Big O, Searching, Sorting and Recursion

Key terms: input, output, steps and complexity

Every algorithm has an input (the data it receives), an output (the result it produces) and a sequence of steps in between. A good algorithm is correct (it gives the right answer for every valid input), finite (it always stops) and clear (each step has one meaning).

• Time complexity describes how the number of steps grows as the input size, written n, grows.
• Space complexity describes how much extra memory the algorithm needs as n grows.
• Worst case is the input that makes the algorithm do the most work; it is the figure most often quoted because it is a safe upper bound.

Algorithms work on data, so the choice of container matters. A lookup in a Python dictionary behaves very differently from a scan through a list, as explained in our guide to data structures explained with examples.

How Big O notation measures growth

Big O notation ignores constant factors and small details and keeps only the term that dominates as n becomes large. An algorithm that takes 3n + 5 steps is simply O(n), because doubling the input roughly doubles the work. Big O does not tell you the exact time in seconds; it tells you how the cost scales.

Linear search versus binary search in Python

Linear search checks each item in turn until it finds the target. It works on any list, sorted or not, and takes O(n) time in the worst case.

def linear_search(items: list[int], target: int) -> int:
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1


def binary_search(items: list[int], target: int) -> int:
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


marks = [12, 25, 31, 47, 58, 63, 79, 88]
print(linear_search(marks, 63))  # 5
print(binary_search(marks, 63))  # 5
print(binary_search(marks, 40))  # -1

Binary search only works on sorted data. It compares the target with the middle item and throws away the half that cannot contain it, so a list of a million items needs about 20 comparisons rather than up to a million. Python's standard library offers the same idea in the bisect module.

Sorting: bubble sort, merge sort and the built-in sort

Bubble sort repeatedly swaps neighbouring items that are in the wrong order. It is easy to understand but takes O(n^2) time. Merge sort splits the list in half, sorts each half and merges the two sorted halves, giving O(n log n) time at the cost of O(n) extra memory.

def bubble_sort(items: list[int]) -> list[int]:
    data = items.copy()
    for end in range(len(data) - 1, 0, -1):
        for i in range(end):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
    return data


def merge_sort(items: list[int]) -> list[int]:
    if len(items) <= 1:          # base case
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]


scores = [42, 7, 19, 88, 3, 56]
print(bubble_sort(scores))   # [3, 7, 19, 42, 56, 88]
print(merge_sort(scores))    # [3, 7, 19, 42, 56, 88]
print(sorted(scores, reverse=True))

In real programs, use the built-in sorted() function or the list.sort() method. Both use a well-tested O(n log n) algorithm, are stable (equal items keep their original order) and accept a key argument, for example sorted(students, key=lambda s: s.marks). Writing your own sort is a learning exercise, not something to ship.

Recursion and the base case

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that returns without calling itself; without one, the calls never stop and Python raises a RecursionError once its call-depth limit is reached.

def factorial(n: int) -> int:
    if n <= 1:                   # base case
        return 1
    return n * factorial(n - 1)  # recursive case moves towards the base case


print(factorial(5))  # 120

Merge sort above is also recursive: a list of one item is the base case. Each call waits on the call stack until the smaller calls return, so deep recursion uses memory. For simple counting problems, a loop is often clearer and lighter.

How to solve a problem with an algorithm, step by step

1. Restate the problem in your own words and write down the exact input and expected output.
2. Work through two or three small examples by hand, including edge cases such as an empty list or a single item.
3. Write the steps in plain language or pseudocode before writing any code.
4. Start with a simple, correct solution, even if it is slow, such as a nested loop.
5. Work out its time and space complexity and decide whether it is fast enough for the realistic input size.
6. Improve it if needed by choosing a better data structure (a set or dictionary) or a better approach (sorting first, binary search, divide and conquer).
7. Test the final version against your hand-worked examples and the edge cases.

If you are new to the language itself, the Python basics guide covers the loops, lists and functions used here.

Time versus space: choosing the trade-off

You can often make an algorithm faster by using more memory. Checking whether a list has duplicates with two nested loops takes O(n^2) time and O(1) extra space. Storing seen values in a set takes O(n) time but O(n) extra space.

def has_duplicates(items: list[str]) -> bool:
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False


print(has_duplicates(["asha", "ravi", "meera", "ravi"]))  # True

Neither choice is always right. On a small device or with huge data sets memory may be the limit; for a web request that must respond quickly, time usually matters more. Measure with realistic data before optimising, and keep the code readable. When something behaves unexpectedly, the techniques in our debugging walkthrough help you trace it.

Practical exercise: compare search and sort on real data

1. Create a list of 100,000 random integers with random.randint.
2. Time linear_search for a value near the end of the list using time.perf_counter().
3. Sort the list with sorted(), then time binary_search for the same value.
4. Time bubble_sort on the first 2,000 items and merge_sort on the same 2,000, then on 4,000, and note how each time changes.

You are done when you have a short table of your timings and can explain, using Big O, why bubble sort slowed down far more than merge sort when the input doubled. To apply the same thinking in a full programming course, the PHP Foundation course teaches programming fundamentals through PHP projects.

Common mistakes

• Running binary search on an unsorted list, which returns wrong answers without raising any error.
• Writing a recursive function without a base case, or with one the input never reaches.
• Treating Big O as exact running time and ignoring that small inputs may favour a simpler algorithm.
• Calling item in some_list inside a loop, which hides an O(n^2) algorithm behind one line.
• Writing a custom sort for production code instead of using the tested built-in sorted().

Frequently asked questions