DEV Community: Saptarshi Sarkar

Key Math Concepts in Data Structures and Algorithms

Saptarshi Sarkar — Sat, 07 Mar 2026 16:39:43 +0000

At the core of data structures and algorithms are fundamental mathematical principles that guide their design and implementation. This article explores key math concepts essential for mastering data structures and algorithms, helping developers write optimized and effective code.

Number Systems

A number system is a structured way of representing numbers using specific symbols and rules. Different number systems are based on different base values (also called the radix).

We are most familiar with the decimal number system, which is used in everyday life. It uses ten digits (0 through 9) to represent all numbers. Because it uses ten distinct digits, its base is 10.

Computers, however, operate using only two digits: 0 and 1. Therefore, they use the binary number system, which has a base of 2. All data inside a computer is ultimately stored and processed in binary form.

The octal number system uses eight digits (0 to 7) so its base is 8. It is used as a more compact way to represent binary numbers, since each octal digit corresponds to a group of three binary digits (bits). Octal is still used in certain areas of computing, such as file permissions in Unix and Linux systems.

The hexadecimal number system uses sixteen symbols: the digits 0–9 and the letters A–F. Because it has sixteen symbols, its base is 16. Each hexadecimal digit corresponds to a group of four binary digits, making it a convenient way to represent memory addresses, machine code, and other low-level data in computers.

The octal number system has a base of 8, which means it uses eight symbols: 0 to 7.

Since 8 = 2³, each octal digit can represent exactly three binary digits (bits). Same goes for hexadecimal number system.

You can learn how to convert between these number systems from this detailed article.

Now, let’s talk about the binary number system. We are familiar with representing positive numbers using unsigned binary. But how do we represent negative numbers? For this, we use the two’s complement method, which is the standard way to represent signed binary numbers.

Two's complement method

Negative of any decimal number is mathematically found by subtracting that number from 0. The same applies to the binary number system. In the signed binary number system, the most significant bit (the leftmost bit) indicates the sign of the number.

See the image below if you are not familiar with the most and least significant bits in the binary representation of a number:

Let’s take the example of decimal 7 whose binary representation is 0111. Its binary number system is stored in 4 bits. Zero can be represented as 0000 (in 4 bits). In 4-bit representation, if a fifth bit is present in the leftmost position, it is discarded due to lack of space. So, we can represent zero as 10000 (the bit 1 will be discarded). Now, 10000 can be written as the sum of 1111 and 1. We can then proceed as follows:

Essentially, the negative of a binary number will be its complement added to 1. This method is called as the two’s complement method.

Bitwise Operators

In the decimal number system, we use arithmetic operators like +, -, *, and / to perform mathematical operations. In computing, numbers are represented in binary, and in addition to arithmetic operators, we also use bitwise operators like &, |, ^, ~, >>, and << to manipulate individual bits. Let’s discuss each of these operators.

AND Operator (&)

This operator performs bit-by-bit AND operation on two values. This means that for each bit in the operands, the resulting bit is set to 1 only if both corresponding bits in the operands are 1; otherwise, it is set to 0.

Observation:

The AND operation of any number with 1 gives the least significant bit (LSB) of that number.

Example: 5 & 1 results in 1 because 101 & 001 gives its LSB, which is 1.

OR Operator (|)

This operator performs a bitwise OR operation between two operands, setting each resulting bit to 1 if at least one of the corresponding bits in the operands is 1; otherwise, it is set to 0.

XOR Operator (^)

XOR stands for exclusive OR. This operator performs a bitwise comparison between two operands, setting each resulting bit to 1 if the corresponding bits in the operands are different; otherwise, it is set to 0.

Observations:

The XOR operation on any number with 1, results in a number where the least significant bit (LSB) is flipped.

Example: 3 ^ 1 results in 2 because 11 ^ 01 changes the LSB to 0 in this case.
The XOR operation on any number with 0 results in the same number.

Example: 4 ^ 0 results in 4 because 100 ^ 000 gives 100, which is 4.
The XOR operation on any number with itself results in 0 because there are no differing bits.

Example: 5 ^ 5 results in 0 because 101 ^ 101 gives 0 as there are no bits that differ.

Complement Operator (~)

The complement operator gives the bitwise inverse of a number, flipping each bit from 0 to 1 and from 1 to 0.

Left Shift Operator (<<)

The left shift operator is a bitwise operator that shifts the bits of a number to the left by a specified number of positions.

Example: 5 << 1 gives 10 because shifting the bits of 5 (which is 101 in binary) one position to the left results in 1010, which is 10 in decimal.

If we shift twice (5 << 2), we would get 20 because shifting the bits of 5 (which is 101 in binary) two positions to the left results in 10100, which is 20 in decimal.

Therefore, each left shift operation effectively multiplies the number by 2 for each position shifted. In general, if the number is shifted k times, it is multiplied by 2^k.

Right Shift Operator (>>)

The right shift operator is a bitwise operator that shifts the bits of a number to the right by a specified number of positions.

Example: 8 >> 1 gives 4 because shifting the bits of 8 (which is 1000 in binary) one position to the right results in 0100, which is 4 in decimal.

If we shift twice (8 >> 2), we would get 2 because shifting the bits of 8 (which is 1000 in binary) two positions to the right results in 0010, which is 2 in decimal.

Therefore, each right shift operation effectively divides the number by 2 for each position shifted. In general, if the number is shifted k times, it is divided by 2^k.

Core Number Theory

Prime Number

A prime number is a natural number greater than 1 with exactly two positive divisors: 1 and itself. To determine if a number is prime, we typically check divisibility from 2 up to n−1 since it is always divisible by 1 and itself.

int n = 24;
boolean isPrime = true;
for (int i = 2; i < n; i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
if (isPrime) {
    System.out.println("Prime");
} else {
    System.out.println("Not prime");
}

The above algorithm makes a maximum of n - 2 (2 to n-1) checks. So, its time complexity is O(N). Let's see if we can optimise it.

If we closely examine the factors of any number, they appear in pairs (one smaller and one larger). Mathematically, we can say that for every divisor d > √n (like d = 6), there exists a corresponding divisor $nd<n\frac {n} {d} < \sqrt n$ (like 4). Therefore, checking beyond √n is redundant.

If we look into the above possible pairs of factors of 24, we can see that we're checking divisibility of each pair twice. It is sufficient to check divisibility only up to √n since √24 ≈ 4.89, checking up to 4 is enough. Hence, we can reduce the number of computations from the order of N to √N.

int n = 24;
boolean isPrime = true;
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
if (isPrime) {
    System.out.println("Prime");
} else {
    System.out.println("Not prime");
}

The time complexity of this algorithm is now O(√N).

Prime Numbers in Range

Let's say we need to find prime numbers between two certain numbers. The simplest idea would be to check if each of the numbers between them is prime or not.

public class Main {
    public static void main(String[] args) {
        int n = 50;
        displayAllPrimes(n);
    }

    public static void displayAllPrimes(int n){
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
    }

    public static boolean isPrime(int n){
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

In the above program, the isPrime() method takes O(√N) to check whether a certain number is prime. The displayAllPrimes() method calls the isPrime() method approximately N times. So, the time complexity of the entire algorithm is O(N√N).

If we carefully observe the numbers we're checking for prime, we'll notice that there are a number of redundant checks. For example, if we already know that 2 is a prime number then its multiples won't be prime.

Similarly for the rest of the numbers, the below image shows the multiples of smaller prime numbers we've checked earlier.

The unmarked numbers turn out to be the prime numbers we're finding in that range of 2 to 50. This is known as the Sieve of Eratosthenes.

public class Sieve {
    public static void main(String[] args) {
        int n = 50;
        boolean[] isComposites = new boolean[n+1]; // size is n+1 to include n 
        sieve(n, isComposites);
    }

    public static void sieve(int n, boolean[] isComposite){
        for (int i = 2; i * i <= n; i++) {
            if (!isComposite[i]) {
                for (int j = 2 * i; j <= n; j += i) {
                    isComposite[j] = true;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

In the program above, we check for multiples up to √N because large numbers can be factored using smaller numbers' multiples.

The number of times the inner loop (the loop responsible for marking the composite numbers) runs for each prime number P is $NP\frac {N} {P}$ . Therefore, total number of times the inner loop runs will be:

Hence, the time complexity of this algorithm is O(N loglog(N)).

Newton Raphson Method

The Newton Raphson method is an iterative method of finding better approximations to the roots of a real-valued function. The best linear approximation to any differential function near the point $x = x_i$ will be its tangent with the equation:

y = f'(x_i)(x - x_i) + f(x_i)

where $x_i$ is the ith iterative approximation of root

The root of the tangent equation will be the next iterative approximation $x_{i+1}$ when it intercepts the x-axis (y = 0).

Now, if we want to find the square root of any number (say n), we can take f(x) = x² - n. The root of that equation will give us the closest approximation of √n.

You can view this animated image from Wikipedia, which visually demonstrates all the iteration of approximated roots of f(x).

Let's try to write a program for finding the approximate square root of any number.

public class NewtonRaphsonSqrt {
    public static void main(String[] args) {
        System.out.println(sqrt(43));
    }

    public static double sqrt(double n) {
        double x = n;
        double root;
        while (true) {
            root = 0.5 * (x + (n/x));

            if (Math.abs(root - x) < 0.5) { // Error threshold, can be adjusted for more precision
                break;
            }
            x = root;
        }
        return root;
    }
}

Reducing the error threshold, currently set at 0.5, will result in a more accurate approximation of the square root.

Modular Arithmetic

It is a system of arithmetic operations for integers where the numbers "wrap around" when exceeding a certain number called as the modulus. For a given integer m ≥ 1, it is called a modulus if the difference of two integers a and b (a - b) is an integer multiple of m i.e. a - b = k*m (where k is an integer). The integers a and b are said to be congruent modulo m and is mathematically denoted by a ≡ b (mod m).

The parentheses mean that (mod m) applies to the entire equation, not just to the right-hand side (here, b). In particular, (a mod m) = (b mod m) is equivalent to a ≡ b (mod m), and this explains why "=" is often used instead of "≡" in this context.

The congruence relation is written as a = b + k*m.

Source: Wikipedia

In programming, we don’t write congruences directly. Instead, we use the % operator, which computes the remainder. The % operator is the practical realization of the congruence relation. For example: 𝑎 ≡ 𝑏 (mod m) ⇔ (a % m) == (b % m) in code.

The range of (a % m) is always in the range ([0, m-1]) when (m > 0). This ensures the remainder is non-negative, which is crucial for consistent modular arithmetic in programming.

Properties:

Addition Property

When adding two numbers, their remainders modulo (m) add up, but if the sum exceeds (m), subtracting (m) (i.e., taking modulo again) brings it back within the valid range.
$\bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
Subtraction Property

Subtraction can lead to negative results, so adding (m) before taking modulo ensures the result stays within ([0, m-1]).
$\bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$
Multiplication Property

Multiplying the remainders and then taking modulo keeps the product within the modular system, preserving equivalence.
$\times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$
Division Property

Division is not straightforward in modular arithmetic. For division by (b) modulo (m) to be valid, (b) must have a modular inverse modulo (m), which exists only if gcd(b, m) = 1.
$m\frac{a}{b} \bmod m = a \times b^{-1} \bmod m = ((a \bmod m) \times (b^{-1} \bmod m)) \bmod m$
Modular multiplicative inverse of an integer b is the solution (which exists only when b and m are coprime) of the below equation:
$ax≡1(modm)ax\equiv 1 {\pmod {m}}$

Bézout's Identity

It is a theorem which related two arbitrary integers with their greatest common divisor (GCD). Mathematically,

where, x and y are integers.

If gcd(a, b) = d, then every integer linear combination ax + by is a multiple of d.

For example, if a = 3 and b = 16, then 3*(-5) + 16*1 = 1 = gcd(3, 16).

Let's take another example: a = 8 and b = 18. Then, 8*(-2) + 18*1 = 2 = gcd(8, 18).

The coefficients x and y can be found using the Extended Euclidean algorithm and the gcd can be calculated using the Euclidean algorithm.

Euclidean Algorithm

The Euclidean Algorithm is one of the oldest and most efficient methods to compute the greatest common divisor (GCD) of two integers. Since Bézout’s identity relies on the GCD, understanding this algorithm is essential. It's based on the principle that if

Effectively, a is reduced by multiples of b until only the remainder is left. Therefore, gcd(a, b) = gcd(b, a % b).

Let’s compute gcd⁡(514, 106) using the Euclidean Algorithm.

We start by dividing the larger number by the smaller one and continue replacing the pair with (b, a % b) until the remainder becomes zero:

514 = 106*4 + 90

→ gcd⁡(514, 106) = gcd⁡(106, 90)
106 = 90*1 + 16

→ gcd⁡(106, 90) = gcd⁡(90, 16)
90 = 16*5 + 10

→ gcd⁡(90, 16) = gcd⁡(16, 10)
16 = 10*1 + 6

→ gcd⁡(16,10) = gcd⁡(10, 6)
10 = 6*1 + 4

→ gcd⁡(10, 6) = gcd⁡(6, 4)
6 = 4*1 + 2

→ gcd⁡(6, 4) = gcd⁡(4, 2)
4 = 2*2 + 0

→ gcd⁡(4, 2) = 2

Therefore, gcd(514, 106) = 2.

public static int gcd(int a, int b) {
    if (a == 0) {
        return b;
    }
    return gcd(b % a, a);
}

We can also calculate the LCM of two numbers using their GCD with the formula:
$LCM(a,b)=∣a×b∣GCD(a,b)\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}$

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

Extended Euclidean Algorithm

This algorithm is an extension of the Euclidean Algorithm which computes the coefficients of the Bézout's identity. We start with the gcd of the two numbers and eventually represent that as a linear combination of those two numbers.

For example, we have found gcd(514, 106) = 2. We start with the last non-zero remainder step: 6 = 4 + 2 ⇒ 2 = 6 - 4.

Then, from previous steps, we can write 6 = 16 - 10 and 4 = 10 - 6. We'll back-substitute them in the above equation.

∴ 2 = (16-10) - (10 - 6) = 16 - 2*10 + 6 = 16 - 2*10 + (16 - 10) = 2*16 - 3*10

We can write 10 as 90 - 16*5 (from Euclidean Algorithm's steps).

∴ 2 = 2*16 - 3*(90 - 16*5) = 17*16 - 3*90

We can write 16 as 106 - 90 (from 2nd step)

∴ 2 = 17*(106 - 90) - 3*90 = 17*106 - 20*90

We can further write 90 as 514 - 106*4.

∴ 2 = 17*106 - 20*(514 - 4*106) = (-20)*514 + 97*106

Hence, (-20)*514 + 97*106 = 2 = gcd(514, 106). So, the coefficients (Bézout's coefficients) of Bézout's identity would be -20 and 97.

We can utilise the recursion stack to keep track of the steps performed in Euclidean Algorithm. Below is the code for this algorithm:

static int gcdExtended(int a, int b, int[] xy) {
    if (a == 0) {
        xy[0] = 0; // x
        xy[1] = 1; // y
        return b;
    }

    int[] temp = new int[2];
    int gcd = gcdExtended(b % a, a, temp);

    // Update x and y using results of recursion
    xy[0] = temp[1] - (b / a) * temp[0];
    xy[1] = temp[0];

    return gcd;
}

Conclusion

In this article, we explored fundamental mathematical concepts that are crucial for understanding and implementing data structures and algorithms. We delved into number systems, including binary, octal, and hexadecimal, and discussed how computers represent numbers using the two's complement method for signed integers. We also covered bitwise operators and their applications in manipulating individual bits of data.

⭐ Check out the DSA GitHub repo for more code examples.

Demystifying Time and Space Complexity for Beginners

Saptarshi Sarkar — Wed, 04 Feb 2026 01:36:53 +0000

Imagine you've just created an algorithm, and it works lightning-fast on your brand-new computer. You're thrilled with the results and can't wait to share your success, so you ask your friend to give it a try. However, when your friend runs the same algorithm on his older computer, it doesn't perform as well and turns out to be quite slow. This unexpected result leaves you both puzzled and curious about what might be causing the difference in speed.

Why We Need Complexity Analysis?

As we saw in the problem mentioned earlier, the same algorithm can take different amounts of time to run depending on the machine it's on. In real-world situations, we often need to compare multiple algorithms to choose the best and fastest one. Hardware differences can lead to incorrect conclusions. That's why complexity analysis was introduced — to standardize the comparison between algorithms by ignoring hardware differences.

The concept of complexity measures how performance changes as the input size increases. We always test with large input sizes to reflect real-world scenarios where we might be dealing with vast amounts of data.

What is Time Complexity?

Time complexity measures how the running time increases as the input size grows. It focuses on the number of operations an algorithm performs, not the actual time it takes.

What is Space Complexity?

Space complexity is a measure of the amount of memory an algorithm uses as the size of the input increases, including both the input space and the auxiliary space (the extra space taken).

I want to point out that in recursion, multiple recursive calls use a certain amount of stack space, which is also considered auxiliary space.

Why do we need Asymptotic Notations?

In practical situations, we often need to compare algorithms to find the most efficient one. Remembering the exact function of time (or space) taken as the input size n changes is challenging. For instance, the time it takes for an algorithm to finish can be expressed as $5n^2 + 3n + 2$ . This is complex and not practical for comparison. So, we use asymptotic notations to simplify these expressions and focus on the most significant factors that affect performance (or in other words, approximate them to a simpler function), making it easier to compare different algorithms.

Big-O Notation

Big-O notation is a mathematical concept used to describe an upper bound on the growth rate of an algorithm’s time or space complexity. Formally, it means that for sufficiently large input size n, the complexity function 𝑓(n) does not grow faster than a constant multiple of another function 𝑔(n).

Mathematically,

f (n) = O (g (n))

if and only if the below condition is satisfied.

\le f(n) \le c.g(n), \ n \ge n_0

where, c is a constant and $n_0$ is the threshold value above which the condition is satisfied for all large numbers.

For example, let’s say $f(n) = 16n^2 + 2n + 3$ .

We need to find a suitable g(n) that will satisfy the condition. So, we can proceed as follows:

Comparing this with the given condition, we get c = 21 and g(n) = n².

If we put n as 1, we get f(1) as 21 and 21n² as 21. So, the equality holds and 1 can be a potential threshold value. We will still check for large values of n like 5 in which case the inequality holds. So, the value of $n_0$ turns out to be 1.

Therefore, $O(n^2) \ \forall \ n \ge 1$ .

If we look at the same problem again, we can argue as follows:

This gives us g(n) as n³. We could choose other higher powers of n, but 21n² is the most accurate approximation of the original function. Therefore, we should always choose the smallest upper bound to get the closest curve fit.

Big-Omega Notation

Big-Omega notation is a mathematical way to express the asymptotic lower bound of a function (time or space complexity). It provides a formal way to describe the minimum time an algorithm will take to complete, regardless of the input size.

Mathematically,

\Omega(g(n))

if and only if the below condition is satisfied.

\ge c.g(n), \ n \ge n_0

where, c is a constant and $n_0$ is the threshold value above which the condition is satisfied for all large numbers.

For example, let’s say $f(n) = 16n^4+13n+12$ .

We can easily conclude that $f(n) >= 16n^4$ . If we put $n = 1$ , then $f (1)$ is 41 which is ≥ 16. Therefore, we can say $\Omega (n^4)$ for all n ≥ 1.

Similarly, as we have seen in the case of Big-O, f(n) is ≥ n³, ≥ n², ≥ n, etc. But we should $n^4$ as g(n) because $16n^4$ is the tightest polynomial that consistently under-approximates f(n) without overshooting.

Big-Theta Notation

Big-Theta notation is a mathematical way to express both the asymptotic lower and the upper bounds of a tightly bounded function (time or space complexity).

Mathematically,

\Theta (g(n))

if and only if the below condition is satisfied.

\le c_1.g(n) \le f(n) \le c_2.g(n), \ n \ge n_0

where, $c_1$ and $c_2$ are constants and $n_0$ is the threshold value above which the condition is satisfied for all large numbers.

For example, let’s say $f(n) = 16n^2 + 12$ .

We can proceed as follows:

16n^2 \le 16n^2 + 12 \le 16 n^2 + 12n^2 \ \implies 16n^2 \le 16n^2 + 12 \le 28 n^2

Comparing this with the aforementioned inequality, we get g(n) = n².

If we set n to 1, the inequality holds true. Checking with the next number, 2, the inequality still holds. Therefore, $n_0$ must be 1.

Hence, we can asymptotically say $\Theta (n^2)$ for all n ≥ 1.

Best, Average and Worst Case

There are three scenarios to consider when analyzing algorithms: the best case, the average case, and the worst case. Of these, the worst case provides the most accurate estimate of the time or space an algorithm will require in the most demanding situation, often reflecting real-world scenarios. Hence, the worst case is the most usually preferred.

How to calculate Time Complexity for iterative programs?

Let’s understand the procedure to calculate time complexity through examples.

Example 0

The below code is for printing first N natural numbers.

for (int i = 1; i <= n; i++) {
    System.out.println(i);
}

In the code snippet above, the loop runs N times (from 1 to N) and each time we are printing a number (which takes a constant amount of time). Therefore, we are performing constant amount of work N times. So, the growth rate will be linear. Hence, this algorithm has a time complexity of O(N).

Example 1

int i = 1;
int s = 1;
while (s <= n) {
    i++;
    s = s + i;
    System.out.println(s);
}

We should analyse the values of i and s to check how many times the print statement (a constant time work) is executed.

In the above table, we can observe that:

3 = 1 + 2 = $2∗(2+1)2\frac {2*(2+1)} {2}$
6 = 1 + 2 + 3 = $3∗(3+1)2\frac {3*(3+1)} {2}$
10 = 1 + 2 + 3 + 4 = $4∗(4+1)2\frac {4*(4+1)} {2}$

So, asymptotically, since constants don't change the growth rate of s, it grows on the order of k². Therefore, we take the values of i and s as k and k² respectively for the kth iteration.

The while loop will stop when s > n, which means k² > n. Therefore, k must be equal to √n. As a result, the constant time task of printing the value of s will happen √n times. Thus, the time complexity of this code snippet is O(√n).

Example 2

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i*i; j++) {
        for (int k = 1; k <= n/2; k++) {
            System.out.println(k);
        }
    }
}

We need to analyze how often the constant task of printing the value of k happens. To do this, we'll create a table showing how many times the loops for i, j, and k run.

The outermost for loop (loop i) runs until i equals n. Therefore, the total time the innermost loop runs will be the sum of the times it executes for each combination of i and j values.

Therefore, the constant work is performed in the order of n⁴. Hence, the time complexity for this code snippet is O(n⁴).

Types of Recurrence Relations

There are two types of recurrence relations:

Linear Recurrence Relation: These express the next term as a linear combination of previous terms (e.g., Fibonacci sequence).
Divide and Conquer Relation: These arise in recursive algorithms where a problem is divided into subproblems, solved recursively, and combined (e.g., Merge Sort, Binary Search).

How to calculate Time Complexity for recursive programs?

There are three ways to calculate time complexity given the recurrence relation:

Back-Substitution Method
Recursive Tree Method
Akra–Bazzi Method

Let’s learn these methods in detail.

Back-Substitution Method

Let’s take the following linear recurrence relation as an example:

We'll start by finding T(n-1) and T(n-2), and then substitute them back into the equation. Next, we'll generalize the equation for the kth substitution and try to substitute the constant given for the base condition (i.e., when n = 0).

Therefore, we can write T(n) as:

Now, T(n-k) will be equal to T(0) when n-k = 0, i.e. when k = n.

$∴T(n)=T(0)+n=1+n\therefore T(n) = T(0) + n = 1 + n$

Hence, time complexity of this T(n) function would be O(N).

Recursive Tree Method

Let’s take the following linear recurrence relation as an example:

We'll try to visualize the recursive calls and the constant values at each call as a recursive tree.

The total time taken for the complete recursive function will be the cumulative sum of work done at each level of recursion, with each level contributing an amount equal to its index (n). Therefore, total time = $1 + 2 + ... + (n - 2) + (n - 1) + n$ = $n∗(n+1)2\frac {n*(n+1)} {2}$ which is a quadratic growth of time. Hence, time complexity will be O(N²).

Let's take an example of a divide-and-conquer recurrence relation and try to solve it using this method.

We’ll again draw the recursive tree to visualise the recursive calls made.

To find the total time complexity, we simply look at the work done across the tree horizontally. At the top level, the work is n. At the second level, we have two branches doing $n/2$ work, which again sums to n. Surprisingly, if you sum the work across any horizontal level of this tree, it always equals n. Therefore, the total time is simply the work per level (n) multiplied by the number of levels (the height of the tree).

To find the total number of levels, we'll assume the last level is the kth level. At the ith level, the input to the function is $n2i\frac {n} {2^i}$ . So, at the last level, $T(n2k)=T(1)T(\frac {n} {2^k}) = T(1)$ , which means $n2k=1\frac {n} {2^k} = 1$ , leading to $k = log_2 n$ .

Hence, time complexity will be O(n*log n).

Akra-Bazzi Method

This method is a generalization of the Master Theorem for divide-and-conquer recurrences. Mathematically, if the function T(x) can be represented as

where:

p must be such that $∑i=1kaibip=1\sum_{i=1}^{k} a_i b_i^p = 1$
$a_i > 0$ and $0 < b_i < 1$ for all i

Then,

For example, let's consider the following recurrence relation, which has been solved using other methods:

Comparing with the standard equation, we get:

$a_1 = 2$
$b1=12b_1 = \frac {1} {2}$
$g (n) = n$

We can proceed as follows, to find the value of p.

Therefore, time complexity of T(n) would be:

How to calculate Space Complexity?

For Iterative Programs

Let's look at the two code snippets below as examples 1 and 2:

// Example 1
int[] arr = {54, 26, 35, 85, 90};
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}
System.out.println("The maximum value in the array is: " + max);

// Example 2
int[] arr = {54, 26, 35, 85, 90};
int[] revArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    revArr[i] = arr[arr.length - 1 - i];
}
for (int num : revArr) {
    System.out.println(num);
}

In the first example, we're finding the maximum element in the array. If we closely analyze the algorithm, it uses only a constant number of extra variables (max and the loop counter i), regardless of the size of the input array. Since the extra space needed does not increase with the input size, the space complexity is O(1).

In the second example, the algorithm reverses the array by creating a new array revArr whose size depends on the input size N. Apart from this array, only a constant number of extra variables (such as loop counters) are used. Since the auxiliary space required grows linearly with the input size, the space complexity is O(N).

We can modify the algorithm to reverse the array in place by performing swap operations between elements from the beginning and end of the array. This approach eliminates the need for an additional array. The algorithm uses only a constant number of extra variables (such as temp and the loop counter), regardless of the input size. Therefore, the auxiliary space complexity of this approach is O(1).

// Modified Example 2
int[] arr = {54, 26, 35, 85, 90};
for (int i = 0; i < arr.length / 2; i++) {
    // Swap to reverse the array in-place
    int temp = arr[i];
    arr[i] = arr[arr.length - 1 - i];
    arr[arr.length - 1 - i] = temp;
}
for (int num : arr) {
    System.out.println(num);
}

For recursive programs

In recursive programs, each recursive function call is added to the call stack, creating a stack frame (or activation record) for each call.

Call Stack is a data structure used in programming languages to manage the functions calls and their execution. It works on LIFO (Last-in, First-out) principle where the most recently called function is executed first and removed from the stack once completed.

Let’s look at the following recurrence relation, which we have already solved for time complexity:

We need to analyze the recursive calls (especially their order). So, we’ll take a look at its recursive tree:

First, the leftmost branches are called, and after they execute, each of these function calls is removed from the call stack, starting from the bottom of the recursive tree. Then, the function calls in their respective right branches are executed. Here is an image of the flow of execution of the leftmost branches:

This is how the call stack would appear until the T(1) function completes its execution:

The total space used in the call stack for executing the leftmost branches is equal to the height of the recursive tree (which is also known as maximum recursion depth), which is log n as calculated before.

This is the maximum space used in the complete execution of the program as for further calls (suppose from T(n/2²) to second T(n/2³)), the stack frames of the previous calls (the series of calls from the first T(n/2³) and T(n/2³) itself) are removed.

This is the complete view of the function calls:

Hence, space complexity would be O(log n).

Conclusion

Understanding time and space complexity is crucial for evaluating and optimizing algorithms, especially as input sizes grow. By analyzing complexity, we can make informed decisions about which algorithms are most efficient, regardless of hardware differences. Asymptotic notations like Big-O, Big-Omega, and Big-Theta provide a standardized way to express these complexities, focusing on the most significant factors affecting performance.

Through examples, we've explored how to calculate time complexity for both iterative and recursive programs, as well as how to determine space complexity. Mastering these concepts allows developers to write more efficient code, ultimately leading to better performance in real-world applications.

What is Recursion? A Comprehensive Overview

Saptarshi Sarkar — Fri, 16 Jan 2026 05:25:33 +0000

A Problem

Let’s start with a problem: I need to print first 10 natural numbers.

There are several ways to solve this problem. But let's say we need to solve it using functions without using loops or calling a function more than once. The simplest way is to call 10 functions, each printing one of the numbers from 1 to 10.

public class Problem {
    public static void main(String[] args) {
        print1();
    }

    public static void print1(){
        System.out.println(1);
        print2();
    }

    public static void print2(){
        System.out.println(2);
        print3();
    }

    public static void print3(){
        System.out.println(3);
        print4();
    }

    public static void print4(){
        System.out.println(4);
        print5();
    }

    public static void print5(){
        System.out.println(5);
        print6();
    }

    public static void print6(){
        System.out.println(6);
        print7();
    }

    public static void print7(){
        System.out.println(7);
        print8();
    }

    public static void print8(){
        System.out.println(8);
        print9();
    }

    public static void print9(){
        System.out.println(9);
        print10();
    }

    public static void print10(){
        System.out.println(10);
    }
}

Let’s try to understand how the function calls are happening internally.

I’ll try to debug that code by putting the debug pointer at the line calling print1() function.

When you start the debug window in IntelliJ IDEA, you can see the function calls in the call stack on the left side of the window.

When print1() function is called, it appears on top of the main() function in the call stack.

After print1() function displays 1 in the output, it calls print2() function and so on. Finally, print10() function gets called.

After printing 10, the print10() call finishes execution, so its stack frame is removed (popped) from the call stack and control returns to the caller (which is print9() function).

Finally, each of the stack frames are removed until the main function completes its execution.

However, the code is messy!

The Idea of Recursion

If we look closely, each of the 10 functions we defined earlier has the same structure. They each print a number and then call the next function in order. If we were given the task to print natural numbers upto a million, defining a million functions would be terrific.

To summarize, we solved the bigger problem of printing the first 10 natural numbers by breaking it down into 10 smaller parts. Each function handles the task of printing one number at a time.

Hence, we can think of recursion as breaking down a problem into sub-problems until it becomes trivial.

If we look at the code again, each function calls the next one until the last function (print10()). So, we can rewrite the function to print the current number and then call itself with the next number in sequence until it reaches number 10.

public class Problem {
    public static void main(String[] args) {
        print(10);
    }

    public static void print(int n) {
        // Base Condition: Exit when n is 0 or negative
        if (n <= 0) {
            return;
        }
        // Recursive call/relation: Calls itself by passing the next smaller element
        print(n - 1);
        // Return Flow / Work after recursion
        System.out.println(n);
    }
}

This is called as recursion, and the print() function is called as recursive function. There are three parts of any recursive function:

Base Condition: The condition where the recursion stops
Recurrence Relation: This relation defines how the problem is reduces to smaller sub-problems.
Return Relationship/Flow: This defines how the result of the smaller sub-problem is used when the function call returns.

Recursive Tree

To better understand how the function call happens, we need to know about recursive tree which is a visual representation of the recursive calls. The below image shows a recursive tree for our program.

Finding a Fibonacci number using recursion

The nth Fibonacci number is equal to the sum of the (n-1)th and (n-2)th Fibonacci numbers. So, the problem of finding the nth Fibonacci number can be broken down to smaller problems. Hence, this problem can be solved using recursion.

We got the following recurrence relation:

F ib o (n) = F ib o (n - 1) + F ib o (n - 2)

So, the recursive tree for Fibo(4) will be:

We know that the first 2 numbers of the Fibonacci series are 0 and 1. So, value of Fibo(1) and Fibo(0) are 1 and 0 respectively. Hence, the function must stop calling itself again when the value of n becomes 1 or 0. Therefore, this becomes the base condition.

Here’s the code for finding nth Fibonacci number using recursion:

public class Problem {
    public static void main(String[] args) {
        System.out.println(fibo(5));
    }

    public static int fibo(int n) {
        // Base Condition
        if (n < 2) {
            return n;
        }
        // Recurrence Relation and Return Relationship
        return fibo(n-1) + fibo(n-2);
    }
}

Using the recursive tree, we can better understand the order of function calls. First, Fibo(4) calls Fibo(3) (since fibo(n-1) is written first), which then calls Fibo(2). Next, Fibo(2) calls Fibo(1). Since no further function call is made, Fibo(1) returns its value as 1.

To calculate the value of Fibo(2), we need the value of Fibo(0), so Fibo(0) is called and returns 0. Then, Fibo(1) is called because it is needed to compute the value of Fibo(3).

The value of Fibo(4) depends on Fibo(2), which in turn depends on Fibo(1) and Fibo(0), leading to those function calls.

Finally, Fibo(4) computes the sum and returns the value as 3.

Tail Recursion

The most important type of recursive function is the tail recursive function. This is a recursive function where the last operation is the recursive call itself. If we rewrite the initial recursive program that prints natural numbers from 1 to 10 using the code below, we can make it a tail recursive function.

public class Problem {
    public static void main(String[] args) {
        print(1, 10);
    }

    public static void print(int current, int n) {
        // Base Condition: Exit when current exceeds n
        if (current > n) {
            return;
        }
        // Print the current value
        System.out.println(current);
        // Tail recursive call
        print(current + 1, n);
    }
}

The recursive Fibonacci function is not a tail recursive function because, after making the Fibo(n-1) and Fibo(n-2) recursive calls, it adds their returned values. Therefore, the last operation is not the recursive call itself.

Binary Search using recursion

In the binary search algorithm, we always check if the middle element is equal to the target element. If the check fails, the search space is cut in half each time. This means the task of checking for equality is done in smaller, reduced sections of the original array. Hence, the binary search algorithm can be implemented using recursion.

The binary search algorithm stops when the equality check is met, so the recursion must end when this condition is satisfied. Therefore, the equality check becomes the base condition.

As the search space of the array is halved each time, the start and end values of the search space are needed in every recursive function call. Therefore, the start and end pointer values will be included in the function parameters. The index of the middle element (mid) depends on the start and end index values, so it doesn't need to be passed to future recursive calls. Therefore, mid will be calculated within the function.

Based on whether the middle element is greater or less than the target element, the function will make its next recursive call with updated start or end pointer values. The result of this call will be the position of the target element if it exists in the array, or an indication that the element is not present.

public class Problem {
    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 72, 88, 99, 101, 123, 145, 167};
        int target = 101;
        int result = binarySearch(arr, target, 0, arr.length - 1);
        System.out.println("Element found at index: " + result);
    }

    public static int binarySearch(int[] arr, int target, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2; // to avoid integer overflow
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, end);
        } else {
            return binarySearch(arr, target, start, mid - 1);
        }
    }
}

We perform two tasks:

Comparing the middle element with the target element. This takes a constant amount of time. So, time complexity of comparison is O(1).
Searching for the target element in half of the previous search space.

So, the recurrence relation would be:

F(\frac {N}{2})

where F is the binary search function and N is the size of the array.

The relation above means that when a target number is provided, a comparison is first made. Then, the number is searched for in half of the previous search space of the array.

Space Complexity

As in recursion, we are calling the function n times and each function call goes in the call stack, so space complexity of a recursive algorithm is not constant.

Conclusion

Recursion is a powerful programming concept that allows complex problems to be broken down into simpler, more manageable sub-problems. By understanding the key components of recursion—base condition, recurrence relation, and return flow—developers can effectively implement recursive solutions for various problems, such as calculating Fibonacci numbers or performing binary searches. While recursion can lead to elegant and concise code, it is important to consider its space complexity due to the call stack usage. Mastering recursion can greatly enhance problem-solving skills and lead to more efficient algorithms.

⭐ Check out the DSA GitHub repo for more code examples.

Cyclic Sort Made Simple: Learn the Basics and How It Works

Saptarshi Sarkar — Sat, 10 Jan 2026 18:30:11 +0000

Cyclic sort is an in-place and unstable sorting algorithm that is specifically designed to efficiently sort arrays where numbers are in a known range like from 1 to N.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

The algorithm works by choosing an element and puts it at its correct index. It starts with the first element.

In the example array, the algorithm chooses the first element 5. Its correct index is 4.

The algorithm swaps 5 with the element at the correct index of 5 i.e. element 2 present at index 4.

The algorithm now checks whether the element at the position of the control variable i is in its correct position: Is 2 in its correct position? No. So, the control variable will not increment its position.

The algorithm will swap 2 with 4 (as the correct index of 2 is index 1).

It will again check: is element 4 is at its correct index? No, it isn’t. The correct index of 4 is index 3.

So, it will swap element 4 with element 3 (as the correct index of element 4 is index 3).

Now, it will check again: is element 3 at its correct index? No, it isn't. The correct index of 3 is index 2.

So, element 3 will be swapped with element 1.

Now, the algorithm checks once again: is element 1 at its correct index? Yes, it is!

So, the algorithm will move to the next index and once again check if that element is at its correct index.

Is element 2 at its correct index? Yes, it is. The algorithm continues this process until it reaches the end of the array.

💡	You might have already realized that the correct index for an element is its value - 1, if the range of numbers in the array is 1 to N.

Space Complexity

As this algorithm is an in-place sorting algorithm, it does not require any auxiliary space. So, its space complexity is O(1).

Time Complexity

We have two scenarios here: the worst case and the best case.

Worst Case

The worst case happens when every number is in the wrong place in an array with a known range (say, 1 to N). The sample array used above, [5, 4, 1, 3, 2], is an example of the worst case. Let's calculate how many times the algorithm performed checks.

In the example array, total 4 swaps and 5 checks were made. After all swaps were performed at the first index, the element at that index was checked once again. Therefore, there were a total of 5 checks.

In general, N - 1 swaps and N checks would be made. As in each swap, 1 check is performed. So, there would be a total of $2 N - 1$ checks made.

Therefore, the worst-case time complexity of cyclic sort algorithm is O(N).

Best Case

The best case happens when the array is sorted in the desired order. In that case, the algorithm checks each element once and does not perform any swaps. Therefore, the best-case complexity is O(N).

Example Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 1, 4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void sort(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            // Assuming range of array is 1 to N
            int correctIndex = arr[i] - 1;
            if (arr[i] != arr[correctIndex]) {
                swap(arr, i, correctIndex);
            } else {
                i++;
            }
        }
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Conclusion

Cyclic sort is a highly efficient algorithm for sorting arrays with elements in a known range, such as from 1 to N. It operates in-place, requiring no additional space, which makes it space-efficient with a complexity of O(1). The algorithm's time complexity is O(N) in both the best and worst cases, making it a reliable choice for sorting tasks where the range of numbers is predetermined. By understanding the mechanics of cyclic sort, you can effectively apply it to relevant sorting problems, optimizing performance and resource usage.

⭐ Check out the DSA GitHub repo for more code examples.

How Insertion Sort Works: Simplified Explanation

Saptarshi Sarkar — Sat, 29 Nov 2025 07:02:29 +0000

Insertion sort is a simple comparison-based sorting algorithm that sorts by repeatedly inserting elements into their correct position. Let's explore how it works in detail.

What is Insertion Sort?

Insertion Sort is a comparison sort algorithm. It divides the array into two parts: the sorted part and the unsorted part. It repeatedly inserts each element from the unsorted part into its correct position in the sorted part of the array.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

The insertion sort algorithm uses two loops: one controls the number of passes (or traversals) through the array, and the other compares adjacent elements and performs swap if needed, starting from the first element of the unsorted section. Let variable i control the number of passes and variable j control the comparison of adjacent elements. As i increases, the sorted section grows, and j helps place each element in its correct position within the sorted section.

💡
Since we are sorting in ascending order, the sorted part of the array is on the left side.

Initially, i should start from index 0. The variable j takes the value i+1 which in the initial case is index 1.

As the sorted region lies behind the initial value of j in each pass, the algorithm compares the jth element with the j-1th element.

It will check: is 9 less than 3? No, it isn’t. So, it will get swapped.

After the swap, the value of j decreases by a unit. As the j-1th element is undefined (error will be thrown if we try to access that element), so j should always be greater than 0.

Now, in the second pass, i increases to 1. j takes the value of 2.

Now, the algorithm checks: is 9 less than 6? No, it is not. So, they will be swapped.

The value of j changes to 1. The algorithm now checks: is 3 less than 6? Yes, it is. So, no swap operation will be performed.

Now, the third pass starts. The value of i changes to 2 and j becomes 3.

Now, the algorithm checks: is 9 less than 10? Yes, it’s. So, no swap operation will be performed.

As we know, the part of the array on the left side of j is already sorted at the beginning of each pass. Therefore, it's unnecessary to check all the way to the leftmost end of the array. If the desired order is found between adjacent elements during comparison, the internal loop can exit for that pass.

Now, starting with the fourth pass, the value of i becomes 3 and that of j becomes 4.

The algorithm now checks: is 10 less than 1? No, it isn’t. So, they will be swapped.

The value of j changes to 3. Now, it checks: is 9 less than 1? No, it isn’t. So, they’ll be swapped.

j is now at index 2. It checks: is 6 less than 1? No, it isn’t. So, they get swapped.

The value of j decreases to 1. Now, it checks: is 3 less than 1? No, it isn’t. So, they get swapped.

Now, the internal loop exits. As j takes the value i+1 and index 5 does not exist, so the maximum value of i should be 3. In general, i must be less than N - 1 where N is the length of the array.

Our array is finally sorted! 😃

Time Complexity

There are two possible scenarios: the best case and the worst case.

Worst Case

The worst case occurs when the array is sorted in the reverse order. Let’s try to find out the total number of comparisons made.

In the 1st pass, only 1 comparison is made.
In the 2nd pass, 2 comparisons are made.
…
In the N-1th pass, N-1 comparisons are made.

So, the total number of comparisons made is:

\sum_{i=1}^{N-1} i = \frac {N*(N-1)}{2} \ = \frac {N^2 - N}{2}

Hence, the time complexity is O(N²) as constants are cancelled, and less dominating terms are removed.

Best Case

The best case occurs when the array is already sorted in the desired order. In that case, there will be utmost 1 comparison made in each pass because the internal loop will break once it finds that the desired order is followed by the adjacent elements while comparing them. Therefore, total number of comparisons made is N-1 where N is the size of the array.

Hence, the time complexity in this scenario is O(N).

Space Complexity

As the insertion sort algorithm is an in-place sorting algorithm, it does not use any auxiliary space. Hence, its space complexity is O(1).

Stability

The insertion sort is a stable sorting algorithm as the original order of the equal elements (or the duplicate elements) is maintained in the final sorted array.

Uses of Insertion Sort

Insertion sort is the most efficient sorting algorithm for small arrays because it is adaptive. Adaptive means that for smaller values of N, the number of comparisons made are reduced and number of swaps performed is also less compared to bubble sort.

It works better when the array is nearly sorted. Hence, it is often used in hybrid sorting algorithms like TimSort and IntroSort.

Example Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {9, 3, 6, 10, 1};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j-1);
                } else {
                    break;
                }
            }
        }
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Conclusion

Insertion sort is a straightforward and efficient algorithm for sorting small arrays. Because of its adaptive nature and its stability, it performs well on nearly sorted arrays. Understanding insertion sort provides a solid foundation for learning more complex sorting techniques.

⭐ Check out the DSA GitHub repo for more code examples.

Selection Sort Simplified: Easy Guide

Saptarshi Sarkar — Tue, 25 Nov 2025 16:38:05 +0000

Selection Sort is a simple sorting algorithm that repeatedly finds the smallest (or the largest) element from the unsorted part and moves it to its correct position.

What is Selection Sort?

Selection sort is a comparison sort algorithm. It repeatedly selects the smallest or largest element from the unsorted part of the array and swaps it with the element at the appropriate index. This is why it is named Selection Sort.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

The selection sort algorithm finds the smallest element of the array at every traversal. Here, the smallest element is 1 so it put 1 at the first position (0th index). Hence, it swaps 1 and 9.

Next, in the following pass, the smallest element is 3. Its correct index is 1. Since it is already in the right place, no swap is needed.

Now the next smallest element from the unsorted part of the array is 5. It must be placed in the 3rd position (2nd index). Hence, the algorithm will swap 9 and 5.

In the next pass, the smallest element of the unsorted part of the array is 8. As 8 is already in its appropriate position, no swap is performed. The last element is not checked because if all the other elements are in their correct positions, then the last element must also be in its correct position.

The array is finally sorted 😃!

💡	Similar procedure will be followed if we start with the largest element.

Time Complexity

The algorithm works in two steps:

Finds the smallest (or the largest) element of the unsorted part of the array
Swap it!

For finding the smallest (or the largest) element of the array, N - 1 comparisons need to be made where N is the size of the array.

In the first traversal, N - 1 comparisons are made. In the second traversal, N - 2 comparisons are made as one element is already sorted. In the third traversal, N - 3 comparisons are made and so on. In the last traversal, only 1 comparison will be made.

Hence, total number of comparisons is

\\ = \frac {(N-1)(N-1+1)}{2} \\ = \frac {N(N-1)}{2} \\ = \frac {N^2 - N} {2}

Therefore, time complexity is O(N²) as constants are cancelled, and less dominating terms are removed.

In both the worst case and the best case, the time complexity is O(N²) as even in the best case, comparisons are made to find the smallest (or the largest) element every time.

Space Complexity

The space complexity of selection sort algorithm is O(1) as no extra space is taken.

Stability

The Selection Sort is not a stable sorting algorithm as it does not maintain the original order of the equal elements (or duplicate elements) in the final sorted array as it was present in the original array.

Example Code

The example code demonstrates two possible implementations of the selection sort algorithm within a single Java file. One method selects the smallest element from the unsorted part of the array during each pass, while the other method selects the largest element.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSortUsingMaxElement(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
        int[] arr2 = {89, 45, 68, 90, 29, 34};
        selectionSortUsingMinElement(arr2);
        System.out.println("Sorted array: " + Arrays.toString(arr2));
    }

    static void selectionSortUsingMaxElement(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // find the maximum element in unsorted part of the array and
            // swap it with correct index
            int lastIndex = arr.length - i - 1;
            int maxIndex = getMaxIndex(arr, 0, lastIndex);
            swap(arr, maxIndex, lastIndex);
        }
    }

    static void selectionSortUsingMinElement(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // find the smallest number in the unsorted part of the array and
            // swap it with the correct index
            int firstIndex = i;
            int minIndex = getMinIndex(arr, firstIndex, arr.length - 1);
            swap(arr, firstIndex, minIndex);
        }
    }

    private static int getMinIndex(int[] arr, int start, int end) {
        int min = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] < arr[min]) {
                min = i;
            }
        }
        return min;
    }

    private static int getMaxIndex(int[] arr, int start, int end) {
        int max = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[max]) {
                max = i;
            }
        }
        return max;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Conclusion

Selection Sort is a straightforward and intuitive sorting algorithm that is easy to understand and implement. This algorithm is used for small datasets. An advantage of this algorithm over bubble sort is that it requires fewer swaps. It is also an in-place sorting algorithm so can be used where memory usage is a concern.

⭐ Check out the DSA GitHub repo for more code examples.

A Beginner's Guide to Bubble Sort Algorithm

Saptarshi Sarkar — Sun, 23 Nov 2025 08:32:22 +0000

Bubble sort (also called as Sinking Sort and Exchange Sort) is a straightforward sorting algorithm that operates by repeatedly comparing and swapping adjacent elements if they are in the wrong order.

What is Bubble Sort?

Bubble Sort is a comparison sort algorithm that organizes elements in a list by repeatedly comparing and swapping adjacent elements if they are in the wrong order. It is named for the way smaller elements "bubble" to the top of the list. The passes through the list are repeated until no swaps have to be performed during a pass.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

As the bubble sort algorithm is a comparison sort algorithm, in each pass (or traversal through the array), it will compare each pair of adjacent elements. We’ll start with the first two elements.

The algorithm checks: is 6 less than 2? No. Then, swap 6 and 2.

Then, the next pair of elements are checked. The algorithm asks: is 6 less than 5? No, it’s not. So, it will swap 6 and 5.

The algorithm picks the next pair of adjacent elements and checks: is 6 less than 8? Yes! Then, it’ll move to the next pair.

The algorithm now checks: is 8 less than 3? No, isn't. So, it’ll swap 8 and 3 elements.

The first pass is now completed. It will go for the next pass.

💡	Notice that the largest element of the list comes at the end of the list in the first pass.

In the second pass, we’ll again start with the first two pair of elements. The algorithm checks: is 2 less than 5? Yes, it is. Then, it checks: is 5 less than 6? Yes!

Then, 6 less than 3? No! So, perform swap.

Next, the algorithm checks: is 6 less than 8? Yes, it is. So, it will go for the next pass.

💡	We notice that in the 2nd pass, the 2nd largest element of the list goes to the 2nd last position of the list.

In the third pass, the algorithm starts by again checking the first two pair of elements. It checks: is 2 less than 5? Yes! Next, it checks: is 5 less than 3? No, perform swap.

Then, the algorithm checks: is 5 less than 6? Yes!

Next, it checks: Is 6 less than 8? Yes!

💡	We again notice that the third largest element of the list comes at the third last position of the list.

The array is finally sorted 😀!

Reducing redundant checks

In the subsequent passes, we notice that rightmost part of the array is getting gradually sorted. So, in the next pass, there is no need to check that sorted part of the array.

Notice that in the first pass, one element gets sorted; in the second pass, 2 elements are sorted and so on. So, in the n-1th pass, only the first element will remain. Hence, we need to run the loop (for passes) n-1 times.

How does the optimized algorithm work?

The algorithm has two loops: the outer loop for the number of passes and the inner loop which compares each pair of adjacent elements and perform swap if required.

We start with i = 0 (the first pass). The pointer variable j goes from 0 till the last element.

Then for i = 1 (the second pass), j runs from 0 to 3rd index as the last element is the largest element (so last element is “sorted”).

Now for i = 2 (the third pass), j runs from 0 to 2nd index as the last 2 elements are sorted.

Now, for i = 3 (the fourth pass), j runs from 0 to 1st index as the rest of the elements are sorted. On comparing the first 2 elements of the array (the only remaining elements), the algorithm finds that they are sorted. Hence, the algorithm ends here.

Generalizing, we get the following results:

counter variable i runs from 0 till n - 1
pointer variable j runs from 0 till n - i - 1

where n is the length of the array.

Space Complexity

As we are not taking up any extra space (like creating extra array or variables), so space complexity of bubble sort is O(1) means constant space complexity. Hence, bubble sort is an in-place sorting algorithm.

Time Complexity

We have two scenarios here: the Best Case and the Worst Case.

Best Case

The best case happens when the array is sorted in the desired order. Now, how do we know if the array is sorted? In the first pass, if no swap operation is performed, then it means that the array is sorted and the algorithm can stop. Hence, total number of comparisons made = N - 1. So, time complexity of bubble sort is O(N).

💡	Remember, constants are ignored in time complexity because want to find a mathematical relationship between time and length of inputs and are not interested in calculating the exact time taken by the algorithm.

Worst Case

The worst case occurs when the array is sorted in the reverse order. Let’s try to find the total number of comparisons made in this case:

In an array of N elements,

In the 1st pass, N - 1 comparisons are made.
In the 2nd pass, N - 2 comparisons are made.
…
In the N - 1th pass, 1 comparison is made.

So, the total number of comparisons is:

\sum_{i = 1}^{N-1} (N - i) = N*(N-1) \ - \frac{N*(N-1)}{2} \\ = \frac{N*(N-1)}{2} \\ = \frac{N^2-N}{2}

Therefore, time complexity is O(N²) as constants are cancelled, and less dominating terms are removed.

Stability of Sorting Algorithm

The stability of a sorting algorithm refers to how it handles the order of equal (or duplicate) elements. If the algorithm maintains the original order of equal elements in the final sorted array, it is called a stable sorting algorithm. Bubble Sort algorithm is one such example.

Example Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 5, 8, 3, -45, 0, 34, 12};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void bubbleSort(int[] arr) {
        boolean swapped = false;
        // run the outer loop for n-1 passes
        for (int i = 0; i < arr.length - 1; i++) {
            // In each subsequent pass, the largest element comes at the last respective index
            for (int j = 1; j < arr.length - i; j++) {
                // swap if the item is smaller than the previous item
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    swapped = true;
                }
            }

            // if you did not swap for a particular pass, it means the array is sorted
            if (!swapped) {
                break;
            }
        }
    }
}

Conclusion

Bubble Sort is a basic yet important sorting algorithm that helps explain how sorting works through comparing and swapping elements. Although it is not very efficient for large datasets because of its O(N²) time complexity in the worst case, it is a great learning tool for beginners to understand the basics of sorting algorithms. Its stability and in-place sorting make it useful for small datasets or when memory usage is a concern.

⭐ Check out the DSA GitHub repo for more code examples.

Mastering Data Cleanup: Unleash the Power of OpenRefine

Saptarshi Sarkar — Mon, 20 Oct 2025 07:27:22 +0000

Real-world data is messy. It has inconsistent spellings, stray characters, and mixed number formats, which can cause problems even with simple analysis. In this post, I will guide you through a practical, beginner-friendly OpenRefine workflow (based on an example from the Hands-On Data Visualization book) to clean a small but intentionally messy sample dataset. By the end, you'll be able to convert noisy numeric fields into proper numbers, cluster and standardize text values, and export a tidy CSV ready for visualization.

TL;DR

This article provides a beginner-friendly guide to using OpenRefine for data cleanup. It covers importing and parsing data, cleaning numeric and text columns, and exporting a tidy dataset. The process includes using facets, transformations, and clustering to standardize and correct data inconsistencies, making it ready for analysis and visualization. The guide is inspired by the "Hands-On Data Visualization" book and includes practical steps and screenshots for clarity.

Prerequisites

You'll need the following tools and files ready before you start the walkthrough:

Latest version of OpenRefine installed
Downloaded CSV file of the sample messy data provided in the Hands-On Data Visualization book

Dataset preview

Before we start cleaning, let’s look at what the raw data actually looks like. The screenshot below shows the first 10 rows of the sample dataset. Notice the inconsistent spellings in the Country column and the mix of symbols and commas in FundingAmount column — we’ll fix all of these with OpenRefine.

Data Cleaning

Now that we’ve explored the dataset, let’s start cleaning it using OpenRefine. In this section, we’ll walk through a few essential steps to turn messy, inconsistent data into a tidy and analysis-ready table. We’ll begin by importing the CSV into OpenRefine, then clean up numeric fields, standardize text values, and finally export a clean version of the dataset.

OpenRefine lets you make these transformations interactively, with instant previews and the ability to undo or redo any step — perfect for exploring and cleaning data safely before analysis.

Step 1: Importing and parsing (Creating a new project)

Start the OpenRefine application. You should see a webpage open like this:
Since we have already downloaded the CSV file of the dataset, we will upload it from our local computer. Click on This Computer → Choose Files to upload our dataset. You can also drag and drop the file there.
Click on Next. This will show the progress of the data upload.
Finally, our dataset is parsed and previewed. Make sure the data is displayed correctly here. If everything looks good, proceed with creating the project by clicking the Create project button.
The project will open and look like this. Since there are 127 rows and only 10 are shown, we'll switch to display all of them by clicking the "500 rows" button. This gives us a complete view of the data for proper analysis and cleaning.

Step 2: Clean numeric column (`FundingAmount`)

Generally, we can use facets to highlight differences in large datasets because manually analyzing each cell for deviations from the expected result is time-consuming. Since the FundingAmount column should contain positive numbers, we can apply a Custom text facet to identify non-numeric cells.

We will need to reduce the whole data set into a smaller data set excluding those that can be converted to positive numbers (numeric datatype). So, we’ll be using the below GREL expression to classify the dataset into two groups — Valid and Invalid based on whether the values can be converted to a positive number.

if(
    isError(value.toNumber()),
    "Invalid",
    if(
        value.toNumber() < 0,
        "Invalid",
        "Valid"
    )
)

Here is what each part of the expression means:

toNumber() function - converts the value to a number (first, the value is converted to a string if it's not already in string format, and then to a number)
isError() function - Takes a GREL expression as input and returns true if the expression results in an error, and false otherwise.
if() function - Takes three arguments in this order: the expression to evaluate, what to return if true, and what to return if false.

We will categorize the entire dataset into two groups:

Valid: if the value can be successfully converted to a positive number
Invalid: if the value cannot be converted to a number or if the converted number is negative

Click on Ok to apply the facet, and we’ll see two choices: Valid and Invalid. We’ll include only the data records labeled as Invalid. Now, the number of rows decreases from 127 to 121 — not a huge reduction, but it helps in focusing on the problematic entries.

Now, we’ll procced with transforming the invalid values by removing redundant commas and spaces, dollar sign, etc.

Click on Edit cells and then on Transform option in the FundingAmount column.
We will now replace the commas, spaces, dollar signs, and any unnecessary characters in the number. The following GREL expression will be used:
```
value.replace(/[a-z$, ]/, "")
```
The regex expression [a-z$, ] matches any lowercase letters, dollar signs, commas, and spaces. The replace() function will replace each of these matches with an empty string.
On applying the transformation, we’ll see that a large part of our dataset has got cleaned. As we have selected only invalid group, only the records containing negative numbers are shown.
We’ll now finally convert the negative numbers to positive ones using the following GREL expression for the transformation:
```
value.toNumber() * -1
```
As soon as we apply the transformation, all the values in the FundingAmount column have been converted to positive numbers. Now, we’ll remove the facet.

Finally, we’ll convert each of the values to Number format using Edit cells → Common transforms → To number option.

Step 3: Standardizing text column (`Country` & `FundingAgency`)

The Country column contains inconsistent spellings and variations of “North Korea” and “South Korea”. Similar cases are also observed in the FundingAgency column.

One of the most powerful features of OpenRefine is clustering which find groups of cell values containing the alternative representation of the same thing.

Click on the arrow-down button of the Country column → Edit Cells → Cluster and edit option.

We're using the default clustering method. You can learn more about each of the clustering methods in OpenRefine’s documentation.
We’ll set the new cell value to North Korea and South Korea accordingly. Finally, we’ll click on Merge selected & Close option.
Let’s check if any cells have value other than North korea and South Korea. We’ll use the following GREL expression for our custom facet to categorize the cell values into Valid and Invalid groups.
```
if ((value == "North Korea").or(value == "South Korea"),
    "Valid",
    "Invalid"
)
```
We’ll select the Invalid choice in facet. We can see that 3 cell values need cleaning.
We'll first replace Nor and xNorth with North so we can use clustering, which is a better method than editing each cell directly, especially for a large number of rows.

The following GREL expression will be used:
```
value.replace(", Nor", " North")
     .replace("xNorth", "North")
```
We’ll first remove the facet because we need to apply clustering to the entire dataset to find similarities. Then, we’ll select the Cluster and edit option and choose the n-Gram fingerprint method with an n-Gram size of 1. We’re choosing the n-Gram fingerprint method because the only difference between South Korea and SouthKorea is a space, and the n-Gram fingerprint method removes all spaces.

Now, we’ll merge those two clusters.

We have now successfully cleaned the Country column.

Similarly, for the FundingAgency column, we’ll apply n-Gram Fingerprint clustering method with n-Gram size as 1.

This clustering method can sometimes produce false positives, so be sure to check the cluster values before merging. Notice that in the second cluster, Department of Defense is included in the cluster of Department of State, which is incorrect. Therefore, we’ll leave the Department of Defense value unchecked while merging.

Using Text facet, we can view the different groups of values in that column. We notice that some values are still messy, like Department - Agriculture and U.S. Agency: International Development. So, we’ll use clustering again. This time, we’ll use the Nearest neighbor clustering method (with the PPM function) because the cell values share some common words, making it helpful to find the nearest neighbor in this case.

We’ll now merge these three clusters. Next, try increasing the radius value to find more nearest neighbors to catch messy data values with slight similarities (like Department of Argic and Department of Agriculture).

I tried setting the radius value to 3.0 and found some correct clusters that I considered merging.

Step 4: Quick sanity checks & facets

To verify whether the complete dataset has been cleaned, we can use the following facets:

Numeric facet on Funding Amount column
Text facet on Country and FundingAgency columns

Upon examining the facets, we see that they are all valid. Therefore, we have successfully cleaned the dataset.

Congratulations on cleaning your first dataset!

Export & reproducibility

You can now export the cleaned dataset into a file (like CSV) or to a database (such as SQL).

To export, click on the Export button in the top right corner. I am choosing CSV as the output file type.

Conclusion

Data cleaning is often the most time-consuming part of data analysis. With OpenRefine, you can make this step both reproducible and efficient.

Acknowledgments & References

This walkthrough was inspired by the Hands-On Data Visualization book by Jack Dougherty and Ilya Ilyankou, which provides the sample dataset and a concise introduction to cleaning data with OpenRefine.

For detailed explanations of OpenRefine’s features, transformations, and architecture, refer to the official OpenRefine Documentation.

Both the book and the documentation are excellent resources if you’d like to explore more advanced data-cleaning techniques and reproducible workflows.

Resources

Hands-On Data Visualization — https://handsondataviz.org
OpenRefine Official Documentation — https://openrefine.org/docs

I learned a lot by following the Hands-On Data Visualization example and exploring OpenRefine’s documentation. If you’re just starting out with data cleaning, these two resources are the perfect next step.

You can also view my cleaned dataset here: Cleaned dataset on Google Sheets

Everything You Need to Know About Binary Search

Saptarshi Sarkar — Sat, 20 Sep 2025 11:31:12 +0000

Binary search is a cornerstone of efficient searching techniques, particularly when dealing with large datasets. Its power lies in its ability to drastically cut down the number of comparisons needed to locate an element, thanks to its divide-and-conquer approach. This article will guide you through the principles of binary search, its practical applications, and how it stands out from other search algorithms.

What is Binary Search?

Binary Search is an efficient algorithm used to find the position of a target element in a sorted array. It works by repeatedly dividing the search space in half, significantly reducing the number of comparisons required.

How does it work?

Suppose we have a sequence of N elements stored in an array. If the sequence is unsorted, the standard approach is to examine every element one by one until we either find the target or reach the end of the dataset. This method is commonly known as Linear Search (or Sequential Search).

When the sequence is sorted, a more efficient binary search algorithm can be used.

If we consider an arbitrary element in a sequence sorted in increasing order with the value m, we can be sure that all elements prior to that have values less than or equal to m, and all elements after it have values greater than or equal to m. Now, the search area is divided into two parts and based on the target number (the one we're looking for), we can choose to search in one of these regions.

Let’s consider the array below for a deeper understanding of its working.

Suppose we need to look for the number 81.

Let start and end represent start and end indices initially set to 0 and n-1 (where n is the size of the array) respectively.

First the algorithm will find the middle element of the array. Let m represent the index of the middle element of the array. Then m will be the integral value of half of the sum of start and end indices.

Mathematically, we can write 👇

floor(\frac{start + end}{2})

Then comes three cases,

If the target equals the middle element, then we have found the item we’re looking for and we return it.
If the target element is less than the middle element, then we’ll need to search again in the first half of the array (i.e. left side of the middle element) as the array is in ascending order.
If the target element is greater than the middle element, then we’ll need to search again in the second half of the array (i.e. right side of the middle element).

In the example, start corresponds to 0 index and end corresponds to index 7. So, m will be 3.

In the first iteration, as 61 is less than our target element 81, we’ll need to search in the right side of 61. So, now our search space will become 👇

start will become 4 (because we’ve already checked that 61 is not equal to 81). Now, m will become 5.

The middle element, 81, is equal to the target element. Therefore, the loop will stop here, returning the index of the target element in the array.

Time Complexity

We have two scenarios here — the best case and the worst cases.

Best Case

Let's say we have an array where the middle element is the same as the target. In this case, the algorithm will make just one comparison, which is the best-case scenario. So, the time complexity in this case will be O(1).

Worst Case

Suppose we have an array with N elements where the target element is not present. So, the algorithm will proceed as follows:

The algorithm will first find the middle element of the entire array. Let’s say that the target element is greater than the middle element, so the search space will be reduced to N/2 (right side of the middle element).

Again, suppose the target element is to the left of the new middle element. The search space will then shrink to N/4, then to N/8, and so on. Eventually, only one element will remain, making the final search space 1. That last element will either match the target element, or it won't, both being worst-case scenarios.

We can visualize the number of comparisons made in each iteration using the following diagram. Let the Kth comparison be the last one.

For the 0th comparison, the search space is N which can be written as $\frac{N}{2^0}$

For 1st comparison, N/2 can be written as $\frac{N}{2^1}$ .

Similarly, N/4 can be written as $\frac{N}{2^4}$ .

and so on. Following the same pattern, we can write 1 as $\frac{N}{2^k}$ .

Therefore,

N = 2^k

Taking $l o g$ on both sides,

\begin{aligned} log\ N = log\ 2^k \\ \Rightarrow log\ N = k\ *\ log\ 2 \\ \therefore k = log_{2}\ (N) \end{aligned}

Hence, total number of comparisons in the worst-case scenario is $Nlog\ N$ . So, the time complexity is O(log N).

Example Code

An example code in Java is shown below.

We cannot use the $\frac{start\ +\ end}{2}$ formula because int has a fixed size limit, and the value of start + end may exceed the maximum value supported by int. Therefore, we use the safer alternative:

start\ +\ \frac{end\ -\ start}{2}

public class Main {
    public static void main(String[] args) {
        int[] arr = {-87, -58, -23, 2, 5, 63, 94, 99, 135, 189};
        int target = 94;
        int index = binarySearch(arr, target);
        System.out.println("Index of " + target + " is " + index);
    }

    // return the index
    // return -1 if the element does not exist
    static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int middle = start + (end - start) / 2;
            if (target < arr[middle]) {
                end = middle - 1;
            } else if (target > arr[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}

Order Agnostic Binary Search

Currently, we have assumed that the array is sorted in ascending order. Now, we will explore an order-agnostic binary search algorithm. This algorithm first checks the order of the sorted array and then performs the search accordingly. Time complexity will remain the same.

The simplest way to check the order of the array is to check the first and the last elements of the array and compare between them.

Example Code

Here’s a sample code for order agnostic binary search algorithm:

public class OrderAgnosticBS {
    public static void main(String[] args) {
        int[] arr1 = {-87, -58, -23, 2, 5, 63, 94, 99, 135, 189};
        int[] arr2 = {157, 100, 65, 52, 37, 24, 18, -4, -36, -58, -88};
        int target1 = 94;
        int target2 = 65;
        int index1 = orderAgnosticBS(arr1, target1);
        System.out.println("[arr1]:  Index of " + target1 + " is " + index1);
        int index2 = orderAgnosticBS(arr2, target2);
        System.out.println("[arr2]: Index of " + target2 + " is " + index2);
    }

    static int orderAgnosticBS(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        // find whether the array is sorted in ascending or descending order
        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
//            int middle = (start + end) / 2; // The value "start + end" might exceed the maximum possible integer value
            int middle = start + (end - start) / 2;

            if (arr[middle] == target) {
                return middle;
            }

            if (isAscending) {
                if (target < arr[middle]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            } else {
                if (target > arr[middle]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            }
        }
        return -1;
    }
}

Searching in Matrix

Suppose in the matrix below, we need to search for the number 98. The simplest way is to go through each element of the matrix by iterating through each row and column using two for loops.

After comparison, we’ll easily get the answer as [1, 3]. In the worst case, the maximum number of comparisons made will be M*N (where M is the number of rows and N is the number of columns). The time complexity would be O(M*N).

If a matrix is given such that it is sorted row wise and column wise, we should think of minimizing the search space in some logical ways.

Let’s say we’re looking for the number 32 in the above array.

We’ll take the smallest element (here 2) as the lower bound and the largest element in the first row as the upper bound (here 23).

Let’s look for the possible cases to eliminate rows and columns to minimize the search space as much as possible:

Case 1: If element is equal to the target, then answer is found.

Case 2: If the element is less than the target, then all the numbers to the left of that element will also be less than the target. So, that particular row is ignored. As 18 < 32, so 1st row is ignored. We then move to 2nd row at [2, 1] position (as last column is eliminated in case 3) where we found the target element.

Case 3: If element is greater than target, column will get reduced. Let’s say if our target is less than 23, then the target will also be less than each of the elements in the last column. So, the last column will be ignored.

Remember, we’ll start searching from first row and last column and keep running the loops until row number < length and column number >= 0.

Time Complexity

The row counter is going from 0 to N-1 and the column counter is going from N-1 to 0 (where N is the total number of rows/columns in the given square matrix). In the worst case, each of the counters will move N times. So, the total number of comparisons made is equal to 2N. Hence, time complexity is O(N).

Space Complexity

As we are not utilising any auxiliary space, so the space complexity would be O(1).

Searching in a Sorted Matrix

When all the elements are strictly sorted in a matrix, we can think of applying a binary search. An Example of such a matrix is given below.

Let’s say our target element is 16.

We can take the middle column and perform binary search on it to reduce the number of rows to be searched (or middle row to reduce the number of columns to be searched).

Hence, we’ll be first applying binary search on 2nd column. Our mid element will be 32.

As 32 > target element 16, so the last 2 rows will be ignored as those have elements greater than 32 and therefore greater than 16.

There will be three cases in binary search:

If the element is equal to the target, we've found our answer.
If the element > target, ignore rows below that element.
If element < target, all rows above it will get ignored.

Remember, there will be two pointers — start and end pointers of row. For example, row-start pointer will be at 0 and row-end will be at 3 indices initially.

In the end, when only two rows will remain, we’ll first check in the mid column’s segment if it contains the required value. In this case, it does so that’s our answer.

Let’s say the target element was 18, then we will need to apply simple binary search in each of the four parts as shown in white coloured shapes below. This is because each of the parts are sorted.

Time Complexity

We’re making comparisons column wise first (by binary search), so the number of comparisons there is log(N) where N is the length of the column. Then, let’s say in the worst case, we apply binary search in rows up to size M. So, number of comparisons will be log(M).

Hence, time complexity would be O(log (N) + log (M)).

Space Complexity

As we are not using any auxiliary space, so space complexity is O(1).

Conclusion

I hope this article has provided you with a clear understanding of binary search and its significance in efficient data searching. Whether you're a beginner or an experienced programmer, mastering binary search can greatly enhance your problem-solving skills and optimize your algorithms. Keep exploring and practicing harnessing the full potential of this fundamental algorithm in your coding journey. Thank you for reading, and happy coding!

⭐ Check out the DSA GitHub repo for more code examples.

💡 Looking to master core algorithms? Check out my deep-dive on 𝗟𝗶𝗻𝗲𝗮𝗿 𝗦𝗲𝗮𝗿𝗰𝗵—step-by-step logic explained visually, edge-case handling (1D, ranges & 2D), and ready-to-run code snippets. Thoughts?

Saptarshi Sarkar — Mon, 04 Aug 2025 17:16:27 +0000

Saptarshi Sarkar

Aug 3 '25

Mastering Linear Search: Learn the Essentials of This Core Algorithm

#algorithms #java #programming #datastructures

Comments

4 min read

Mastering Linear Search: Learn the Essentials of This Core Algorithm

Saptarshi Sarkar — Sun, 03 Aug 2025 18:06:31 +0000

Among the various search algorithms, Linear Search stands out as the most fundamental. In this article, we will delve into the workings of Linear Search and break down its implementation step by step.

What is Linear Search?

Linear Search is a simple search algorithm that examines each element in a list one by one until it finds the desired element or reaches the end of the list. It doesn't need the data to be sorted.

How does it work?

Let’s use the array below as an example and say we need to search for the number 63.

The algorithm will first check the first element, 80.

The index pointer will ask: “Is 80 the number we need?”

The algorithm responds: “No, it’s not!”

The index pointer moves to the next element, 14.

The pointer asks, “Is 14 the number we’re looking for?”

The algorithm replies, “No.”

It will then move to the next element, 15.

The pointer asks again, “Is 15 the number we want?”

The algorithm responds, “No, it isn’t!”

It then moves to the next number, 63.

The pointer asks, “Is 63 our desired number?”

The algorithm responds, “Yes, it is,” and returns the index of the number.

In some case, if the element is not found, we can return -1 as it is an invalid index.

As we go through the array, we are basically using either a for loop or a for-each loop (also known as an enhanced for loop).

Time Complexity

We have two scenarios — the best and the worst cases.

Best Case

The best case happens when the element we're looking for is the first one in the array.

The algorithm finds the required element at the first position, resulting in the fastest possible search time. The time complexity in this situation is O(1) (constant).

Worst Case

The worst case occurs when the element we’re searching for is not present in the whole array.

The algorithm has to traverse the whole array, checking each element one by one until it reaches the end. The time complexity in this situation is O(N), where N is the size of the array.

Space Complexity

Space complexity is O(1) i.e. constant space complexity.

Constant space complexity (O(1)) means that the amount of memory the algorithm uses does not grow with the size of the input. No matter how big the input gets, the algorithm uses the same fixed amount of space.

Example code

Here is a simple Java code for the linear search algorithm:

public class Main {
    public static void main(String[] args) {
        int[] nums = {52, 89, 12, 1, 65, 34, 90, -29, -83, -11};
        int target = 90;
        int index = linearSearch(nums, target);
        System.out.println("Index of " + target + " is: " + index);
    }

    // search in the array and return the index of the element if found, otherwise return -1
    private static int linearSearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1; // Return -1 if the array is null or empty
        }

        // Iterate through each element in the array
        for (int index = 0; index < arr.length; index++) {
            // Check if the current element equals the target
            int element = arr[index];
            if (element == target) {
                return index; // Return the index if the element is found
            }
        }
        return -1; // Return -1 if the target is not found in the array
    }
}

Linear Search Techniques

Linear Search in a Given Range

Suppose we want to find the number 63 in the same array, but only if it exists within the index range of 2 to 4, inclusive.

In this case, the loop will start at index 2 and end at index 4. It will check each element in that range until it either finds the desired element or reaches the end of the loop.

Below is an example of searching within a specific range of an array using this algorithm:

public class SearchInRange {
    public static void main(String[] args) {
        int[] arr = {18, 12, -7, 25, 31, 8, 0, 19};
        int target = 8;
        System.out.println(linearSearchInRange(arr, target, 2, 6));
    }

    private static int linearSearchInRange(int[] arr, int target, int start, int end) {
        if (arr == null || arr.length == 0 || start < 0 || end >= arr.length || start > end) {
            return -1; // Handle invalid input
        }

        for (int index = start; index <= end; index++) {
            if (arr[index] == target) {
                return index; // Target found, return index
            }
        }
        return -1; // Target not found in the specified range
    }
}

Linear Search in a 2D Array

Let’s consider the following 2D Array:

Clearly, we will need two loops—one to go through each row and another to iterate over each element within those rows. Then, we’ll compare those elements with the target. If it matches, we’ll return it.

Here's a simple code example of how to perform a linear search on a 2D array:

import java.util.Arrays;

public class SearchIn2DArray {
    public static void main(String[] args) {
        int[][] arr = {
            {80, 14, 15, 63},
            {12, 45, 67},
            {34, 78, 90, 11, 22, 33},
            {44, 54, 62, 83, 59}
        };
        int target = 90;
        int[] result = searchIn2DArray(arr, target);
        System.out.println("Location of " + target + " is: " + Arrays.toString(result));
    }

    private static int[] searchIn2DArray(int[][] arr, int target) {
        for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr[row].length; col++) {
                if (arr[row][col] == target) {
                    return new int[] {row, col};
                }
            }
        }
        return new int[] {-1, -1};
    }
}

Conclusion

In conclusion, Linear Search is a simple algorithm that is easy to understand and implement. While not the most efficient for large datasets, it is useful for basic search operations. Whether searching in a range or a 2D array, Linear Search offers a clear method for finding elements. Its fundamental principles are the basis for more advanced search techniques.

⭐ Check out the DSA GitHub repo for more code examples.