DEV Community: Saptarshi Sarkar

The Anatomy of Catastrophic Forgetting

Saptarshi Sarkar — Wed, 10 Jun 2026 12:51:26 +0000

We train a model on handwritten digit classification. 99% accuracy. Then we train the same model on a new task — say, fashion item recognition. We go back and test it on digits. 34% accuracy. It has completely forgotten. Not gradually, not partially — almost entirely.

What Just Happened?

We trained a CNN on MNIST digits — 99.2% accuracy. After fine‑tuning on Fashion MNIST, it reached 91.1% accuracy. But when re‑evaluated on MNIST, accuracy collapsed to 33.9%. This collapse is catastrophic forgetting: the model’s weights shifted to optimize for the new task, erasing the old solution.

Why did training on more data make the model worse at something it already knew?

MNIST is handwritten digits (0–9). Fashion MNIST is clothing items like shirts and shoes. Both are 28×28 grayscale images, but the tasks are distinct.

Why Does It Happen?

The core issue is that the model relies on the same set of weights for both tasks. There is no separation or dedicated memory; every parameter is shared. When training shifts from Task A (MNIST digits) to Task B (Fashion MNIST), gradient descent simply minimizes the loss on the data it sees at that moment. It has no awareness that Task A ever existed.

In the loss landscape, imagine two parabolic bowls: one for Task A and one for Task B. The optimum for Task A lies at $θ_{A *}$ , while Task B's optimum is at $θ_{B *}$ . As training on Task B progresses, the weights $θ$ move towards $θ_{B *}$ . This movement inevitably raises the loss for Task A because its minimum is left behind.

The root cause is the shared weight space. Gradient descent is a stateless optimizer; it only follows the current gradient signal. Since the minima for Task A and Task B are far apart, there is no single configuration of $θ$ that satisfies both tasks simultaneously. This is why catastrophic forgetting occurs.

Weight space can be visualized as an N-dimensional space, where each axis corresponds to one parameter. Every point in this space represents a full set of weights i.e., a complete model. The loss function defines a landscape over this space, and training is the process of moving through it along gradient directions.

Why "Catastrophic"?

Human memory forgets gradually and selectively; you forget less-used memories slowly over time, and the forgetting is usually partial. Neural networks, by contrast, forget catastrophically — performance can collapse within just a few epochs, dropping from near‑perfect accuracy (e.g., 99%) to far lower levels (e.g., 34%) in a single training run. This forgetting is non‑selective: the entire task distribution degrades, not just edge cases.

The underlying tension is the stability–plasticity dilemma. High plasticity allows fast learning of new tasks but destabilizes old ones, leading to catastrophic forgetting. Low plasticity preserves prior knowledge but prevents effective learning of new tasks. Continual learning research seeks to balance this trade‑off.

How Do We Measure It?

The standard evaluation protocol in continual learning is simple but powerful. We train on Task 1 and record accuracy $R_{1, 1}$ . Then we train on Task 2 and record accuracy on both tasks, $R_{2, 1}$ and $R_{2, 1}$ . We continue for N tasks. This produces an accuracy matrix $R_{i, j}$ , where each entry is the accuracy on task j after training on task i.

From this matrix, we define Backward Transfer (BWT):

B W T = \frac{1}{N - 1} Σ_{j = 1 N - 1} (R_{N, j} - R_{j, j})

A negative BWT means catastrophic forgetting: performance on earlier tasks has degraded. In our demo, accuracy on Task A dropped from 99.2% to 33.9% after training Task B, giving a strongly negative BWT of -65.3%.

There is also Forward Transfer (FWT), which asks whether learning Task B helps Task A’s starting point. It is less central to catastrophic forgetting, but worth noting for completeness.

Why Not Just Retrain?

The first instinct is obvious: why not just keep all the data and retrain the model from scratch every time new data arrives? It sounds simple but in practice, it’s impossible.

Privacy and regulation: In domains like medical imaging, GDPR, HIPAA and other privacy acts forbid indefinite storage. Once a patient’s scan is used, it may need to be deleted. You can’t just “keep everything.”
Storage limits: Modern datasets are massive. Retaining every sample forever is infeasible.
Compute cost: Retraining a large model from scratch each time is prohibitively expensive. Imagine re‑training GPT‑scale models weekly; the cost is humongous.
Streaming data: Some data exists only in a stream (sensor feeds, financial ticks) and is never stored. If you don’t learn it as it arrives, it’s gone.
Real‑time systems: In robotics, finance, or autonomous driving, models must adapt continuously without pausing for full retraining.

This is why continual learning exists as a distinct field: to make adaptation possible under these constraints. The open question is the one that drives the research forward: can we teach a network to learn new things without forgetting old ones, the way humans do?

Try it yourself

Curious to see catastrophic forgetting in action?

See the demo on Colab
Explore the full code on GitHub

From Hackathon Wreckage to Production-Ready: How I Rebuilt My Kubernetes Attack Path Visualiser with GitHub Copilot

Saptarshi Sarkar — Fri, 05 Jun 2026 08:41:02 +0000

This is a submission for the GitHub Finish-Up-A-Thon Challenge

What I Built

Security teams managing Kubernetes clusters face a brutal reality: the cluster's attack surface is a complex web of interconnected resources — pods, service accounts, RBAC bindings, secrets, nodes — and understanding how an attacker could move between them is genuinely hard. Most tools either give you a flat list of CVEs or a sea of alerts with no context about what actually matters.

The idea behind K8s Attack Map is different and, I think, beautifully intuitive: model the entire Kubernetes cluster as a graph, where nodes are cluster resources and edges are relationships that an attacker could exploit. Once you have a graph, you get the entire arsenal of graph algorithms for free — Dijkstra for finding the most dangerous attack path, BFS for mapping blast radius, graph ablation for identifying the single node or edge whose removal destroys the most attack paths. It turns a hard security problem into an elegant graph theory problem.

I built the first version of this at a hackathon organised by my college. Our team of four chose the Kubernetes attack path visualiser track. The code worked — barely — but it was held together with duct tape: broken risk scoring, no real test coverage, incomplete docs, and a messy architecture that made every change feel risky. We didn't win. I shelved the project.

Two weeks later, curiosity pulled me back. That intuition — graph theory maps perfectly onto how attackers move through a cluster — wouldn't let go. So I opened GitHub Copilot and decided to do it right.

GitHub Repository: github.com/SaptarshiSarkar12/K8sAttackMap

Demo

Screenshot of tool output using live cluster configuration	Screenshot of executive section of pdf report
Screenshot of interactive graph visualisation of cluster
Screenshot of attack paths discovered

The Comeback Story

Where It Started: The Hackathon Code

The hackathon version worked well enough for a demo, but it had deep structural problems that I discovered only after stepping back.

The biggest flaw: a completely wrong EdgeRiskScorer. The original scorer assigned risk based entirely on the edge relationship string — things like "admin-grant" getting a score of 9.8, "reaches" getting 3.0. It knew nothing about the actual security properties of the source or target nodes. A privileged pod exec-ing into a secret was scored the same as a non-privileged pod doing the same thing. The friction values fed into Dijkstra were essentially made-up numbers with no grounding in real security context.

// Old approach: just matching relationship strings
case "admin-grant", "admin-over", "grants-access-to" -> { return 9.8; }
case "reaches", "routes-to", "calls" -> { return 3.0; }

Other major problems I found:

No SecurityFacts model — security properties of nodes (privileged containers, hostPID, RBAC wildcards, credential material) weren't captured structurally
TrivyCache saved scan results but had no proper workspace isolation — the cache path was hardcoded relative to a vague "app directory" with no cross-platform support and no path traversal protection
ANSI colour output was hardcoded — it would spray escape sequences into CI logs, pipes, and terminals that didn't support them
No EdgeType enum — relationship types were raw strings scattered across the codebase, making refactoring a nightmare
The analysis logic (attack paths, blast radius, choke point detection) was tangled into Main.java instead of separated into its own layer
The PDF report was barebones — useful for developers, unreadable by anyone else
Zero tests. Not a single JUnit test.

The Rebuild: What Changed

After Copilot audited the full codebase, the flaw list was long. I sketched a new architecture, shared it with Copilot, and we went back and forth refining it to align with Java best practices. Here is what the finished version looks like.

1. A Completely Redesigned EdgeRiskScorer

The new scorer starts from node-level SecurityFacts and builds friction values that actually reflect security reality. A privileged container reduces friction by 2.0 (easier for an attacker to move). An RBAC wildcard verb on the target reduces friction further. NODE_ESCAPE and EXEC_INTO edge types carry their own base friction adjustments. Friction is clamped to [0.1, 25.0] for numeric stability. The Dijkstra path found now genuinely represents the path of least resistance for an attacker.

// New approach: security facts drive friction
if (sourceFacts.isPrivilegedContainer()) friction -= 2.0;
if (sourceFacts.isHostPID() || sourceFacts.isHostNetwork()) friction -= 1.5;
if (targetFacts.isRbacHasEscalate() || targetFacts.isRbacHasBind()) friction -= 2.5;
if (targetFacts.isCredentialMaterial()) friction -= 1.8;

2. Trivy Cache with Cross-Platform Workspace Isolation

One of the features I personally implemented is proper centralised caching for Trivy image scans. Scan results (CVSS scores and CVE IDs) are now persisted to ~/.k8sattackmap on Linux/macOS and %LOCALAPPDATA%\k8sattackmap on Windows. The WorkspaceManager validates paths against traversal attacks (.. sequences, separator characters) and verifies the resolved path stays within the base directory.

This means if you scan the same container image twice — maybe across different analysis runs on the same cluster — the expensive Trivy call is skipped and the cached result is reused instantly.

3. NO_COLOR and FORCE_COLOR Support

With Colour	Without Colour

I added full support for the NO_COLOR and FORCE_COLOR environment variable standards, plus a --no-color CLI flag. The TerminalCapabilities class detects CI environments, non-TTY output (pipes, file redirection), and the TERM=dumb case. When colours are disabled, ConsoleColors.disableColors() sets all ANSI escape constants to empty strings — so all the existing output code stays unchanged and just naturally produces plain text.

4. A Proper Analysis Architecture

The monolithic Main.java was dismantled. Analysis now flows through a clean layered structure:

AnalysisOrchestrator
 ├── analysis/graph/       → AttackPathDiscovery, Dijkstra, PrivilegeLoopDetector
 ├── analysis/blast/       → BlastRadiusAnalyzer
 ├── analysis/chokepoint/  → ChokePointIdentifier, ChokePointRemediationAdvisor
 └── analysis/remediation/ → ImpactRemediationAdvisor

Each component is independently testable. The AnalysisOrchestrator coordinates them and produces a structured AnalysisResult.

5. A Much Better PDF Report

Old PDF Report	New PDF Report

Copilot was invaluable here. The old PDF was a developer dump — raw node lists, edge tables, and numbers without explanation. The new report has a proper executive summary section explaining the cluster's overall security posture in plain language, a risk heatmap, prioritised findings with severity context, and a technical section with actual kubectl remediation commands for each finding. The idea: a CISO reads the first half, an SRE acts on the second half.

6. JUnit Test Coverage

Tests Started	Tests Completed

We designed test suites for every meaningful component: EdgeRiskScorerTest, AttackPathDiscoveryTest, BlastRadiusAnalyzerTest, ChokePointIdentifierTest, DijkstraTest, PrivilegeLoopDetectorTest, K8sJsonParserTest, CommandParserTest, and more. Starting from zero tests to having a complete test pyramid covering the security-critical paths felt like the project finally growing up.

7. A modern website featuring elegant, developer-friendly documentation

Previously, there was no website (with docs) for this project. GitHub copilot created the complete website and ensured the design is consistent with the project logo colour palate. It used Next.Js with fumadocs to create this good looking and accessible website. The website design was working for mobile phones from the start!

View the live website: https://k8sattackmap.vercel.app/

My Experience with GitHub Copilot

I want to be honest about this because I think the experience was genuinely interesting rather than just "Copilot wrote the code."

The most useful thing Copilot did at the very start was the audit. I asked it to read through the hackathon code and identify structural and correctness issues. The list it produced was long and surprisingly accurate — it caught the false positive risk scoring problem, the lack of security context in nodes, the string-based edge type fragility, the missing workspace isolation, the absence of tests. Some of these I suspected; others I had missed entirely. Having that comprehensive list upfront let me design the new architecture with all the problems in mind rather than discovering them one by one mid-rebuild.

The architecture review was the second genuinely valuable moment. I drew up my proposed new package structure and class responsibilities and shared it with Copilot. It pushed back on a few naming choices (the original design had some non-standard Java conventions), suggested splitting AnalysisResult from AnalysisInput more cleanly, and recommended the AnalysisOrchestrator as an explicit coordination layer rather than having the CLI command parser call analysis code directly.

For implementation, we mostly pair-programmed. I wrote the core logic for the new EdgeRiskScorer, the WorkspaceManager path safety checks, the NO_COLOR/FORCE_COLOR terminal detection, and the Trivy cache improvements myself — these felt like the security-critical pieces where I wanted to think carefully rather than accept suggestions blindly. For the BlastRadiusAnalyzer, ChokePointRemediationAdvisor, the PDF report templates, and the JUnit tests, Copilot drafted the structure and I reviewed and adjusted. The tests in particular — Copilot is very good at generating test cases that cover edge conditions you might not think to write yourself.

The one place I pushed back on Copilot significantly was the PDF report design. Its first drafts were still too technical — good structure, but the executive summary read like a developer wrote it. I had to be very explicit: "Write this paragraph as if explaining to a VP of Engineering who has never seen a Kubernetes cluster. No jargon. Tell them what the risk means to the business, not what the RBAC binding is." That iterative prompting to get the tone right took several rounds, but the result was worth it.

Overall: Copilot dramatically shortened the time from "identified problem" to "working solution" — especially for boilerplate, test structure, and documentation. But the architectural thinking, the security-specific design decisions, and the judgment calls about what actually matters still needed to come from me. That felt like the right balance.

If you're working on Kubernetes security tooling or just interested in the graph-theory-as-security-analysis approach, I'd love to hear from you. The project is open source — issues, ideas, and PRs are very welcome.

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 $\frac{n}{d} < 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 $\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.
$(a + b) mod m = ((a mod m) + (b mod m)) mod m$
Subtraction Property

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

Multiplying the remainders and then taking modulo keeps the product within the modular system, preserving equivalence.
$(a \times b) mod m = ((a mod m) \times (b mod m)) mod 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.
$\frac{a}{b} mod m = a \times b^{- 1} mod m = ((a mod m) \times (b^{- 1} mod m)) mod m$
Modular multiplicative inverse of an integer b is the solution (which exists only when b and m are coprime) of the below equation:
$a x \equiv 1 (mod 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) = \frac{∣ a \times b ∣}{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 $5 n^{2} + 3 n + 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.

0 \leq f (n) \leq c . g (n), n \geq 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) = 16 n^{2} + 2 n + 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, $f (n) = O (n^{2}) \forall n \geq 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,

f (n) = Ω (g (n))

if and only if the below condition is satisfied.

f (n) \geq c . g (n), n \geq 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) = 16 n^{4} + 13 n + 12$ .

We can easily conclude that $f (n) >= 16 n^{4}$ . If we put $n = 1$ , then $f (1)$ is 41 which is ≥ 16. Therefore, we can say $f (n) = Ω (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 $16 n^{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,

f (n) = Θ (g (n))

if and only if the below condition is satisfied.

0 \leq c_{1} . g (n) \leq f (n) \leq c_{2} . g (n), n \geq 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) = 16 n^{2} + 12$ .

We can proceed as follows:

16 n^{2} \leq 16 n^{2} + 12 \leq 16 n^{2} + 12 n^{2} ⟹ 16 n^{2} \leq 16 n^{2} + 12 \leq 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 $f (n) = Θ (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 = $\frac{2 * ( 2 + 1 )}{2}$
6 = 1 + 2 + 3 = $\frac{3 * ( 3 + 1 )}{2}$
10 = 1 + 2 + 3 + 4 = $\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$

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$ = $\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 $\frac{n}{2 ^{i}}$ . So, at the last level, $T (\frac{n}{2 ^{k}}) = T (1)$ , which means $\frac{n}{2 ^{k}} = 1$ , leading to $k = l o g_{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 $\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$
$b_{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 (N) = O (1) + 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:

i = 1 \sum 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

1 + 2 + ... + (N - 1) = \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:

i = 1 \sum 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 👇

m = f l oor (\frac{s t a r t + e n d}{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,

l o g N = l o g 2^{k} \Rightarrow l o g N = k * l o g 2 ∴ k = l o g_{2} (N)

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

Example Code

An example code in Java is shown below.

We cannot use the $mi d = \frac{s t a r t + e n d}{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:

mi d = s t a r t + \frac{e n d - s t a r t}{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

4 min read