Introduction to Algorithms

Analogy categoryAnalogies

Introduction

An algorithm is a finite, unambiguous sequence of steps that transforms an input into a desired output. Every piece of software you use, from a search engine ranking web pages to a GPS app finding the shortest route, is built on algorithms. Studying algorithms teaches you how to solve problems systematically, predict how a solution will behave as inputs grow, and choose between competing approaches with confidence rather than guesswork.

🏏

Cricket analogy: Just as a bowler follows a finite, precise sequence of steps in their run-up, delivery stride, and release to bowl a legal ball, an algorithm is a finite, unambiguous sequence of steps transforming an input into a desired output.

Key Concepts

A well-formed algorithm has several defining properties: it must be finite (it terminates after a limited number of steps), definite (each step is precisely and unambiguously specified), effective (each step is basic enough to be carried out exactly), and it must accept zero or more inputs and produce at least one output. Correctness means the algorithm produces the right output for every valid input, including edge cases like empty collections, duplicate values, or already-sorted data. Efficiency is usually measured in terms of time (how many operations it performs) and space (how much extra memory it needs), and these two often trade off against each other.

🏏

Cricket analogy: A well-formed bowling action must be finite (the run-up ends), definite (each stride is precisely repeatable), and effective (each step is simple enough to execute); correctness means getting a legal delivery even against left-handers or on a rain-affected pitch, and efficiency trades off pace versus control.

Example

python

def linear_search(items, target):
    """Return the index of target in items, or -1 if not found."""
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1


def binary_search(sorted_items, target):
    """Return the index of target in a sorted list, or -1 if not found."""
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


numbers = [4, 1, 9, 7, 3]
print(linear_search(numbers, 7))       # 3
print(binary_search(sorted(numbers), 7))  # 4 (index in sorted list [1,3,4,7,9])

Analysis

Both functions solve the same problem, finding a target value, but they make different assumptions and have different costs. Linear search checks every element one at a time and works on any list, taking time proportional to the list's length in the worst case. Binary search requires the input to be sorted first, but then it repeatedly halves the search space, making it dramatically faster on large inputs. This comparison illustrates the central theme of algorithm study: the same problem can have multiple valid solutions, and choosing the right one depends on the structure of your data and the constraints you are working under.

🏏

Cricket analogy: Scouting for a player by watching every domestic match one at a time is linear search — it works but is slow; consulting a pre-sorted ranking list and jumping straight to the top bracket is binary search, dramatically faster but only works because the list was sorted first.

Key Takeaways

An algorithm is a finite, well-defined sequence of steps that maps input to output.
Correctness (always giving the right answer) and efficiency (time and space cost) are the two pillars of algorithm evaluation.
The same problem can have multiple algorithms; the best choice depends on data properties and constraints such as whether the input is already sorted.
Understanding algorithms lets you reason about performance before writing or profiling code.

Practice what you learned

1. Which property is NOT required for a valid algorithm?

2. Why does binary search require the input list to be sorted?

3. In the worst case, how does linear search's cost scale with the size of the input list?

4. What does it mean for an algorithm to be 'correct'?

Was this page helpful?

Algorithm Analysis and Complexity

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#IntroductionToAlgorithms#Key#Concepts#Example#Analysis#StudyNotes#SkillVeris