Introduction
An algorithm is a finite, precisely defined sequence of steps that takes some input and produces a correct output, in a way that a machine (or a person) can follow without needing to make judgment calls. It is not the same as a program: an algorithm is the underlying idea or method, while a program is that method written out in a specific programming language so a computer can execute it. The same algorithm can be implemented in many different programming languages.
Cricket analogy: A bowling coach's drill sheet describing exactly how to bowl a yorker step by step is the underlying method, while a specific player executing those steps in their own action is the implementation, just as an algorithm is the idea and a program is that idea written in a specific language.
Explanation
For a sequence of steps to qualify as an algorithm, it needs to be finite (it must eventually stop), well-defined (each step is unambiguous), and correct (it produces the right output for every valid input, not just some). An algorithm that works on the examples you tried but has an edge case where it fails or loops forever is not correct, even if it looks right most of the time. Correctness has to be reasoned about for all valid inputs, not just the ones you happened to test.
Cricket analogy: A run-chase plan that works for every over-count scenario a captain considers, including the very last over with one wicket in hand, is correct, but a plan that only works for 'normal' overs and breaks down in a rare tail-end scenario is not correct just because it worked in the matches tried so far.
Efficiency is the other axis an algorithm is judged on: how its running time or memory use grows as the input size grows. This growth rate is usually described with Big O notation, which captures the dominant term of the growth and ignores constant factors — an O(n) algorithm's work grows roughly in proportion to input size n, while an O(n^2) algorithm's work grows roughly with the square of n, meaning it becomes dramatically slower on large inputs even if it was fine on small ones.
Cricket analogy: Signing one extra net bowler for a training session adds roughly proportional extra coaching time, an O(n) growth, but pairing every net bowler against every batter in a round-robin for feedback grows with the square of the squad size, an O(n^2) growth that becomes unmanageable as the squad expands.
def linear_search(items, target):
# O(n): checks each item once, at most n comparisons
for i, value in enumerate(items):
if value == target:
return i
return -1
def has_duplicate_naive(items):
# O(n^2): compares every pair of items
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
Example
Linear search, which checks each element of a list one by one until it finds the target or reaches the end, is O(n): in the worst case it examines every element exactly once, so doubling the list roughly doubles the work. A naive duplicate-finder that compares every item against every other item is O(n^2): doubling the list roughly quadruples the number of comparisons, because both the outer and inner loop scale with n.
Cricket analogy: Checking a squad list one player at a time to find a specific name is like linear search: doubling the squad size roughly doubles the checks, O(n); but comparing every player's kit size against every other player's to find a duplicate size is like the naive duplicate-finder, quadrupling the comparisons when the squad doubles, O(n^2).
Analysis
Big O describes worst-case growth trend, not exact runtime in seconds — an O(n) algorithm on a slow machine can still be slower in absolute terms than an O(n^2) algorithm on a fast machine for small n. The comparison matters most as n grows large.
Key Takeaways
- An algorithm is a finite, well-defined sequence of steps that produces a correct output for every valid input.
- An algorithm is distinct from a program: the algorithm is the idea, the program is that idea implemented in a specific language.
- Correctness must hold for all valid inputs, including edge cases, not just the examples that happened to be tested.
- Big O notation describes how an algorithm's time or memory use grows as input size grows, ignoring constant factors.
- O(n) work grows proportionally with input size; O(n^2) work grows with the square of input size, becoming much slower on large inputs.
Practice what you learned
1. What distinguishes an algorithm from a program?
2. What does it mean for an algorithm to be 'correct'?
3. What does Big O notation primarily describe?
4. If an algorithm is O(n^2), what happens to its work when the input size doubles?
5. Why is linear search considered O(n)?
Was this page helpful?
You May Also Like
What Is OOP
An introduction to object-oriented programming, covering classes, objects, encapsulation, inheritance, and polymorphism.
What Is an API
An overview of application programming interfaces, how they define a contract between systems, and how REST APIs use HTTP.
What Is JSON
An introduction to JSON's syntax and data types, and why it became the standard format for exchanging structured data between systems.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics