Basics of Algorithms

2.1What is an Algorithm?

Consider computing the area of a circle with radius 10. On a calculator, the "algorithm" is the sequence of key presses; in Python, the same idea becomes a program.

As a calculator algorithm

1. Type 10
2. Type the multiply key
3. Type 10
4. Press the equal/enter key
5. Type the multiply key
6. Type π
7. Press the equal key again
8. Display the output

As Python code

import math

# Define the radius of the circle
radius = 10

# Calculate the area of the circle
area = math.pi * radius**2

# Print the result
print("The area of the circle with radius", radius, "is:", area)

2.2Algorithm vs Program

Before solving a problem, we usually write a possible solution on a piece of paper in our native language — that written solution is the algorithm. When translated into a programming language for a computer to execute, it becomes a program.

2.3The Life of a Programmer

1. Identify a problem.
2. Come up with an algorithm to solve it.
3. Represent the algorithm as a program, using a chosen programming language.
4. Execute the program on a computer.
5. If an error is found → go back to step 2.
6. No error (desired output received) → deliver the output.
7. Go to step 1 :)

2.4Sorting Algorithms

Can you find the smallest number in 53, 21, 38? Easy. Now try the same with a hundred shuffled numbers — the difficulty is not the comparison itself, but the lack of organisation. Sorting turns unorganised data into organised data, after which questions like "what is the smallest element?" become trivial.

Where sorting is used

• E-commerce websites — sorting algorithms arrange products in search results by relevance, price, ratings, or popularity.
• Flight booking systems — flight options are organised by price, departure time, duration, or number of stops so that suitable flights can be found.
• Trending videos — finding the trending videos on platforms like YouTube.

2.5Bubble Sort

Bubble sort is one of the simplest sorting algorithms and forms the foundation for understanding other sorting algorithms. In each pass, adjacent elements are compared and swapped if they are out of order — the largest remaining element "bubbles" to the end of the array.

How it works

1. Start from the first and second elements (i = j − 1, with i = 0, j = 1).
2. If the first element is greater than the next one, swap them.
3. Move to the next pair of adjacent elements (i += 1, j += 1) and repeat the compare-and-swap.
4. Repeat until the end of the array — this completes one pass.
5. Repeat the passes until the entire array is sorted.

Pseudocode

Outer loop: k = 1 to n−1        # n−1 iterations
    Inner loop: j = 1 to n−1    # n−1 comparisons per pass
        i = j − 1
        if A[i] > A[j]:
            temp = A[i]
            A[i] = A[j]
            A[j] = temp

Worked example — input: 19, 18, 14, 61, 9

Pass 1: 19,18,14,61,9 → 18,19,14,61,9 → 18,14,19,61,9 → 18,14,19,61,9 → 18,14,19,9,61 (61 reaches the end).

Pass 2 gives 14,18,19,9,61 → 14,18,9,19,61; pass 3 gives 14,9,18,19,61; pass 4 gives the sorted array 9,14,18,19,61.

2.6Optimised Bubble Sort

A computer can compare numbers very quickly — so why worry about 16 comparisons? Because for large input sizes the wasted work grows rapidly. Three successive optimisations reduce the number of comparisons.

Optimisation 1 — shrink the range after each pass

After pass k, the last k elements are already in place, so the inner loop does not need to revisit them. Setting n = n − 1 after each pass reduces the work.

Outer loop: k = 1 to N−1
    Inner loop: j = 1 to n−1
        i = j − 1
        if A[i] > A[j]:
            temp = A[i]; A[i] = A[j]; A[j] = temp
    n = n − 1                      # skip the sorted tail

Optimisation 2 — stop early when no swap occurs

If a full pass completes without a single swap, the array is already sorted and we can stop. A boolean swap flag captures this.

swap = true
while (swap):
    swap = false
    Inner loop: j = 1 to n−1
        if A[j−1] > A[j]:
            temp = A[j−1]; A[j−1] = A[j]; A[j] = temp
            swap = true
    n = n − 1

Example — input 99, 1, 2, 3, 4: after the first pass the array is 1, 2, 3, 4, 99; the second pass makes no swaps, so the algorithm halts after 4 + 3 = 7 comparisons instead of 10.

Optimisation 3 — remember where the last swap happened

Everything after the position of the last swap is already in order, so the next pass only needs to run up to that point. Store it in m and bound the inner loop by it.

swap = true
while (swap):
    swap = false
    Inner loop: j = 1 to m
        if A[j−1] > A[j]:
            temp = A[j−1]; A[j−1] = A[j]; A[j] = temp
            m = j − 1              # last swap position
            swap = true

Example — input 3, 2, 1, 7, 8: the first pass sorts the front and the last swap occurs early, so the total drops to 4 + 1 = 5 comparisons.

2.7Algorithm Analysis

The resources of interest include:

• Time
• Memory
• Communication bandwidth
• Energy
• CPU registers

What performance depends on

The measured performance of an algorithm depends on:

• Compiler / interpreter
• Computing device
• Input size / type
• Libraries
• Background processes running on the machine

2.8Time Complexity

• Constant time — execution time is fixed, irrespective of input size.
• Linear time — execution time grows linearly with input size.
• Other complexities — quadratic, logarithmic, and so on.

Constant-time operations at the machine level

Consider the statement a = a + b. At a high level it is a single assignment and addition; at the machine level it breaks down as:

MOV R1, a     ; load 'a' into register R1   (fetch, decode, execute, write-back)
MOV R2, b     ; load 'b' into register R2
ADD R1, R2    ; perform the addition
MOV a, R1     ; store the result back to 'a'

Each instruction (MOV, ADD) takes some number of CPU cycles, and the total time is the sum of the individual instruction times — a constant, independent of the input's size and type.

Examples of constant-time statements

int x = 10;
int y = x + 5;
int z = arr[5];
void printMessage() { printf("Hello, World!\n"); }
int result = a & b;   // bitwise AND
return x;

2.9Analysing Loops

Take a simple for loop:

for (int i = 0; i < n; i++) {
    sum += i;
}

Break its cost down statement by statement:

Total time = initialisation + (condition checks + increments + body executions) = 3n + 1 ≈ n. A loop counting down (for (int i = n; 0 < i; i--)) costs the same: n.

Nested loops

for (int i = 0; i < n; i++) {        // outer loop: n times
    for (int j = 0; j < n; j++) {    // inner loop: n times per outer iteration
        sum += i + j;                // executed n × n times
    }
}

Total time = outer × inner = n × n = n².

2.10Loop Examples — Find the Complexity

Work through each example on paper first, then press + show answer to check yourself.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { sum += i + j; }
    sum += i + j;
    for (int k = 0; k < n; k++) { sum += i + j + k; }
}

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            sum += i + j + k;

p = 0;
for (int i = 1; p < n; i++) {
    p = p + i;
}

for (int i = 1; i < n; i = i * 2) {
    p = p + i;
}

for (int i = n; 1 < i; i = i / 2) {
    p = p + i;
}

for (int i = 1; i * i < n; i = i + 1) {
    p = p + i;
}

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j = j * 2) {
        sum += i + j;
    }
}

for (int i = 1; i < n; i = i * 2) {
    p = p + 1;                     // p becomes ≈ log n
}
for (int j = 1; j < p; j = j * 2) {
    sum += i + j;                  // second loop's complexity?
}

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < i; j++) {
        sum += i + j;
    }
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        sum += i + j;
    }
}

for (int i = 1; i < n; i = i * 3) {
    p = p + i;
}

for (int i = 1; i * i * i < n; i = i + 1) {
    p = p + i;
}

2.11Characteristics of an Algorithm

• Input — takes zero or more inputs.
• Output — produces at least one output.
• Definiteness — no vague statements; every step is precisely defined.
• Finiteness — it must stop after a finite number of steps.
• Effectiveness — every step must be basic enough to be carried out.

2.12Beyond Sorting — Algorithms for…

Are there only sorting algorithms? Far from it. Algorithms drive:

• Determining gene sequences
• Finding the best route for downloading data from the internet
• Finding the shortest path in the Zomato app
• Cryptography
• Handling millions of connection requests (e.g., by Jio Hotstar)
• Many more…

2.13Classification of Algorithms

2.14Algorithm Design Paradigms

2.15Algorithms as a Technology

If computers were infinitely fast and computer memory were free, would you have any reason to study algorithms?

2.16Machine Learning vs Algorithms

Machine learning automates algorithm design for complex, poorly understood problems — but it does not replace traditional algorithms, especially for tasks where efficient solutions already exist.

During training

• The ML system learns a model from data (e.g., a decision tree).
• This learning process itself uses optimisation algorithms (like gradient descent).

After training

• The model takes input and follows a set of steps (e.g., matrix multiplication in a neural network) to produce output — which is exactly an algorithm.

2.17Hard Problems

For some problems, no polynomial-time algorithm is known. Examples:

• Travelling Salesman Problem (TSP)
• Resource allocation in edge and cloud computing environments
• 0/1 Knapsack problem
• Graph colouring problem