Table of content:

1. What is an Algorithm?

In Computer Science, an algorithm is a well-defined sequence of steps or instructions used to solve a problem or perform a task.

In simpler language: An algorithm is a set of instructions that tells a computer how to transform some input into the desired output.

When we write a computer program, the computer needs more than just data. It needs:

Data to work with.
A Data Structure to organize the data it works on.
An Algorithm that tells it what operations to perform on that data.

Mental model: Data → Data Structure → Algorithm → Result

Example: Student scores → [82, 95, 71, 88, 90] → Algorithm examines the scores → Result: Highest score = 95

The scores are the data. The array organizes the data. The algorithm describes the steps used to find the highest score.

Algorithms Are Everywhere:

Application	Algorithmic Task
Google Search	Determine which pages are most relevant
Google Maps	Find useful routes
YouTube	Recommend videos
Banking	Detect suspicious transactions
E-commerce	Recommend products
Games	Determine how characters behave
Social media	Select content for a feed
Compression	Reduce file sizes
Databases	Search, organize, and retrieve information
Operating systems	Schedule processes

Different Problems Need Different Algorithms:

There is no single algorithm that solves every problem. Computer scientists have developed families of algorithmic techniques. You do not need to understand each one yet. For now, simply recognize that different problems require different ways of thinking. Later, each of these can be studied individually.

Algorithmic Area	General Purpose
Searching	Find something
Sorting	Arrange information
Traversal	Visit elements systematically
Recursion	Solve a problem using smaller versions of itself
Divide and Conquer	Split a problem into smaller problems
Greedy	Make locally useful choices
Dynamic Programming	Reuse solutions to repeated subproblems
Backtracking	Explore possibilities and undo unsuccessful choices
Graph Algorithms	Work with connected objects and relationships

Characteristics of a Good Algorithm:

Property	Meaning
Clear	Every step should be understandable and unambiguous
Finite	It must eventually stop
Correct	It should produce the expected result
Defined Input	It should know what information it receives
Defined Output	It should know what result it must produce
Efficient	It should use reasonable amounts of time and memory

Example of a Good Algorithm:

Suppose we want to find the largest number in: [4, 9, 2, 7, 6]

Algorithm

Set the first number as the current maximum.
Examine each remaining number.
If a number is greater than the current maximum, update the maximum.
After all numbers have been checked, return the maximum.

Why Is This a Good Algorithm?

Property	How the Algorithm Satisfies It
Clear	Each step is precise and unambiguous.
Finite	It stops after checking every element once.
Correct	It returns the largest value in the array.
Defined Input	It receives a non-empty array of comparable numbers.
Defined Output	It returns the largest number in the array.
Efficient	It checks each element once: `O(n)` time and `O(1)` extra space.

2. Problem vs Algorithm

Concept	Meaning
Problem	What we want to accomplish or solve
Data Structure	How the data needed for the problem is organized and stored
Algorithm	The step-by-step procedure used to solve the problem
Program	The actual code that implements the Data Structure and Algorithm to perform a task

3. How Data Structures and Algorithms Work Together

Data Structures and Algorithms are closely connected. A Data Structure determines how data is organized. An Algorithm determines what we do with that organized data.

Imagine a library containing thousands of books. If the books were simply thrown into a room, finding a particular book would be difficult. Instead, libraries organize books. The organization makes operations easier. Once the books are organized, we still need a procedure for finding one.

A Data Structure serves a similar purpose inside a computer. It organizes information/data so algorithms can work with it effectively. Choosing an appropriate data structure can reduce the time or memory required by an algorithm.

Computer Example:
To implement “undo” feature in a text editor

Use a Stack Data Structure

Algorithm: Push each edit onto the stack and pop the most recent edit when undoing.

A Stack's Last In, First Out (LIFO) behavior makes undo operations natural and efficient.

4. Same Problem ⇒ Multiple Algorithms

Another important concept is that a problem usually does not have only one possible solution.

Suppose we need to find a person's name in a collection.

Algorithm A might examine names one by one using array Data Structure. O(n) time complexity.

Algorithm B might take advantage of how the information is organized in Hash Table and take advantage of fast lookup in that Data Structure. O(1) time complexity.

5. Why the Data Structure Matters

In the example above, both approaches can find the correct person's name. However, one may require significantly less work than the other.

Choosing an appropriate Data Structure can reduce the time or memory required by an algorithm.

Data Structures and Algorithms work together. They should be chosen based on the problem and the operations that need to be efficient. A good algorithm paired with an inappropriate Data Structure may still perform poorly.

This leads to an important question:

How do we compare the efficiency of different algorithms?

That is where Big O notation becomes important.

6. Big O Notation: Measuring Efficiency

Big O Notation describes how the running time or memory usage of an algorithm grows as the input size (n) increases.

It helps us:

Compare the efficiency of different algorithms.

Describe how an algorithm scales as the input becomes larger.

Analyze best-case, average-case, or worst-case growth when applicable.

Focus on the dominant growth rate by ignoring constant factors and lower-order terms.

How Does It Relate to Algorithms?

The same problem can often be solved using different algorithms, and those algorithms may have very different time or space complexities.

For example:

Problem	Algorithm	Time Complexity
Search for an element	Linear Search	`O(n)`
	Binary Search on sorted data	`O(log n)`
Sort elements	Bubble Sort	`O(n²)` worst case
	Merge Sort	`O(n log n)`
Find the largest element	Linear Scan	`O(n)`
Generate all subsets	Backtracking / Subset Generation	`O(2ⁿ)`
Generate all permutations	Backtracking / Permutation Generation	`O(n!)`

As the input grows, the difference between these growth rates can become very large.

For example, searching through one million sorted elements:

Linear Search may examine up to about 1,000,000 elements.

Binary Search needs only about 20 comparisons.

This is why two algorithms that produce the same correct result can perform very differently on large inputs.

Common Big O Complexities

Big O	Name	Growth	Algorithm Example
`O(1)`	Constant	Does not grow with `n`	Accessing a known position or performing a fixed operation
`O(log n)`	Logarithmic	Very slow growth	Binary Search
`O(n)`	Linear	Grows proportionally with `n`	Linear Search
`O(n log n)`	Linearithmic	Slightly faster growth than linear	Merge Sort, Heap Sort
`O(n²)`	Quadratic	Grows quickly	Bubble Sort, checking all pairs
`O(2ⁿ)`	Exponential	Grows very quickly	Generating all subsets
`O(n!)`	Factorial	Grows extremely quickly	Generating all permutations

Time and Space Complexity:

Algorithm efficiency is commonly analyzed in two ways:

Time Complexity: How the number of operations grows as the input size increases.

Space Complexity: How the amount of additional memory required by the algorithm grows as the input size increases.

An algorithm may use more memory to reduce running time, or use less memory while requiring more computation. Therefore, choosing an algorithm often involves balancing time and space efficiency.

Key Idea: Big O helps us compare algorithms by describing how their resource requirements grow as the input becomes larger.

Time-Space Tradeoff: Using extra memory can reduce running time by avoiding repeated work. When memory is available, a small increase in space for a significant improvement in time complexity is often a good tradeoff.

** For a more detailed explanation of Big O Notation, see our Big O Notation description.

What is an Algorithm Method