Definition
- Time complexity – describes how the running time of an algorithm grows as the input size grows.
- Space complexity – describes how the amount of extra memory grows with input size.
- Big-O notation – captures the dominant growth rate while ignoring constant factors and lower-order terms.
- Upper bound – Big-O gives an upper bound on growth, letting you compare algorithms independently of hardware.
- Practical use – predict how a solution behaves when data goes from a thousand rows to ten million.
Imagine National Bank of India has a ledger and Rajesh wants to find an account. If the ledger is an unsorted list and he flips through every card one by one, a million customers means up to a million flips: linear time. If the cards are sorted and he uses the phone-book trick of opening the middle and halving each time, a million customers take only about twenty checks: logarithmic time. Big-O is just a way of saying "as the bank grows to millions of customers, how much slower does this method get?"
Understanding the Concepts
What is Big-O notation?
Big-O focuses on the dominant term as input size n becomes large. If an algorithm does 3n + 100 operations, we call it O(n), because for large n the 3 and the 100 do not matter. We always drop constant multipliers and lower-order terms. We usually care about the worst case.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.List;
public class BigOBasics {
// O(n): one pass through the list
public static BigDecimal sumTransactions(List<BigDecimal> txns) {
BigDecimal total = BigDecimal.ZERO; // +1 assignment
for (BigDecimal txn : txns) { // n iterations
total = total.add(txn); // +1 per iteration
}
return total; // Total: ~n operations = O(n)
}
}
What is O(1) constant time?
The work does not depend on input size at all. Looking up a value in a HashMap by key is O(1). In banking, fetching Rajesh's cached balance by account id from a map is constant time no matter how many customers exist.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class BalanceCache {
private final Map<String, BigDecimal> cache = new HashMap<>();
public void put(String accountId, BigDecimal balance) {
cache.put(accountId, balance); // O(1)
}
public BigDecimal get(String accountId) {
return cache.get(accountId); // O(1) – regardless of cache size
}
}
What is O(log n) logarithmic time?
The work grows very slowly, roughly by one step each time the input doubles. Binary search and TreeMap lookup are O(log n). A million entries take only about twenty comparisons.
package com.bank.service;
import java.math.BigDecimal;
import java.util.TreeMap;
public class SortedAccountLookup {
// TreeMap: O(log n) lookup, sorted by balance
private final TreeMap<BigDecimal, String> byBalance = new TreeMap<>();
public void add(String accountId, BigDecimal balance) {
byBalance.put(balance, accountId); // O(log n)
}
public String highestBalance() {
return byBalance.lastEntry().getValue(); // O(log n)
}
}
What is O(n) linear time?
The work grows in direct proportion to input size. Scanning every transaction in a list once to sum the total is O(n).
package com.bank.service;
import java.math.BigDecimal;
import java.util.List;
public class TransactionSummarizer {
// O(n): visits every transaction exactly once
public BigDecimal totalDebits(List<BigDecimal> transactions) {
BigDecimal sum = BigDecimal.ZERO;
for (BigDecimal txn : transactions) {
if (txn.signum() < 0) {
sum = sum.add(txn.abs());
}
}
return sum;
}
}
What is O(n log n)?
Doing linear work a logarithmic number of times. This is the complexity of good sorting. Collections.sort uses a merge-sort variant that is O(n log n).
package com.bank.service;
import java.math.BigDecimal;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class TransactionSorter {
// O(n log n): sorting the day's transactions by amount
public void sortByAmount(List<BigDecimal> transactions) {
Collections.sort(transactions, Comparator.naturalOrder());
}
}
What is O(n squared) quadratic time?
The work grows with the square of the input, typically from a nested loop. Comparing every transaction with every other to find duplicates naively is O(n squared).
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DuplicateDetector {
// O(n^2): naive nested loop – SLOW for large input
public List<BigDecimal> findDuplicatesSlow(List<BigDecimal> txns) {
List<BigDecimal> duplicates = new ArrayList<>();
for (int i = 0; i < txns.size(); i++) {
for (int j = i + 1; j < txns.size(); j++) {
if (txns.get(i).equals(txns.get(j))) {
duplicates.add(txns.get(i));
}
}
}
return duplicates; // 10,000 items = 50 million comparisons
}
// O(n): HashSet approach – FAST
public List<BigDecimal> findDuplicatesFast(List<BigDecimal> txns) {
Set<BigDecimal> seen = new HashSet<>();
List<BigDecimal> duplicates = new ArrayList<>();
for (BigDecimal txn : txns) {
if (!seen.add(txn)) {
duplicates.add(txn);
}
}
return duplicates; // 10,000 items = ~10,000 operations
}
}
What is space complexity?
Space complexity counts extra memory, not time, and usually excludes the input itself.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class SpaceComplexityExamples {
// O(1) space: uses a fixed number of variables
public BigDecimal sum(List<BigDecimal> txns) {
BigDecimal total = BigDecimal.ZERO; // just one variable
for (BigDecimal txn : txns) {
total = total.add(txn);
}
return total;
}
// O(n) space: builds a new map of all accounts
public Map<String, BigDecimal> buildCache(List<String> ids, List<BigDecimal> balances) {
Map<String, BigDecimal> cache = new HashMap<>(); // grows with input
for (int i = 0; i < ids.size(); i++) {
cache.put(ids.get(i), balances.get(i));
}
return cache;
}
}
Recursion also costs space: each call adds a stack frame, so recursion depth of n is O(n) space.
What is the time-space trade-off?
Caching precomputed account balances in a map uses O(n) extra memory to turn repeated O(n) recomputation into O(1) lookups.
package com.bank.service;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BalanceService {
private final Map<String, BigDecimal> cache = new HashMap<>();
// Without cache: O(n) every time we need a balance
public BigDecimal computeBalance(String accountId, List<BigDecimal> txns) {
BigDecimal balance = BigDecimal.ZERO;
for (BigDecimal txn : txns) {
balance = balance.add(txn);
}
return balance;
}
// With cache: O(n) once to build, then O(1) per lookup
public BigDecimal getCachedBalance(String accountId) {
return cache.getOrDefault(accountId, BigDecimal.ZERO);
}
}
What are common Big-O classes at a glance?
| Complexity | Name | Banking Example |
|---|---|---|
| O(1) | Constant | HashMap balance lookup |
| O(log n) | Logarithmic | TreeMap sorted lookup |
| O(n) | Linear | Sum all transactions |
| O(n log n) | Linearithmic | Sort daily transactions |
| O(n^2) | Quadratic | Naive duplicate detection |
| O(2^n) | Exponential | Brute-force subset problems |
What should a senior engineer know?
Big-O hides constant factors that can matter in practice. An O(n log n) algorithm with a huge constant can be slower than an O(n squared) one for small n. Cache-friendliness and memory locality affect real speed beyond the Big-O class.
Amortized complexity matters: adding to an ArrayList is amortized O(1) even though an occasional resize is O(n), because the expensive resizes are rare and spread out.
package com.bank.demo;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class AmortizedDemo {
public static void main(String[] args) {
List<BigDecimal> transactions = new ArrayList<>();
// ArrayList.add is amortized O(1)
// Occasional resize is O(n), but it doubles capacity,
// so resizes become exponentially rare
for (int i = 0; i < 1_000_000; i++) {
transactions.add(new BigDecimal(i));
}
System.out.println("Added " + transactions.size() + " transactions");
}
}
Added 1000000 transactions
Big-O is the primary tool for reasoning about scale, but you still measure on real data for the final word.
Visual Overview
Big-O Growth Rates (slow to fast growth) ───────────────────────────────────────── O(1) ─────────────────────── constant O(log n) ───────────/ logarithmic O(n) ─────────/ linear O(n log n) ────────/ linearithmic O(n^2) ──────/ quadratic O(2^n) ────/ exponential Banking Examples: ┌───────────────────────────────────────────┐ │ O(1) HashMap.get(accountId) │ │ O(log n) TreeMap.get(balance) │ │ O(n) sum all transactions │ │ O(n log n) sort daily transactions │ │ O(n^2) naive duplicate detection │ └───────────────────────────────────────────┘ Time-Space Trade-off: ┌──────────┐ ┌──────────┐ │ Compute │ │ Cache │ │ O(n) │ vs │ O(1) │ lookup │ O(1) │ │ O(n) │ memory │ space │ │ space │ └──────────┘ └──────────┘
Key Takeaway
Time complexity describes how an algorithm's running time grows as the input grows, and space complexity describes how its extra memory grows. Both are expressed in Big-O notation, which captures the dominant growth rate and ignores constant factors and lower-order terms, so Rajesh can compare algorithms independently of hardware and predict behaviour as data scales.
The common classes Rajesh rattles off with banking examples are these. Constant time O(1) is a HashMap lookup of an account by id, regardless of how many customers exist. Logarithmic O(log n) is a TreeMap lookup, growing by only one step each time the data doubles. Linear O(n) is summing every transaction once. O(n log n) is sorting the day's transactions. Quadratic O(n squared) is a naive double loop comparing every transaction with every other.
At National Bank of India, the fraud duplicate-check was written as a nested double loop, which is O(n squared). It ran fine on a fifty-row test file but took minutes on the real hundred-thousand-row file, because a hundred thousand squared is ten billion comparisons. Rajesh rewrote it as a single pass using a HashSet, which is O(n) time with O(n) extra memory, and it finished in a fraction of a second.
Space complexity follows the same logic but counts memory. The important idea is the time-space trade-off: caching precomputed balances in a map spends O(n) extra memory to turn repeated O(n) recomputation into O(1) lookups. Big-O hides constant factors and cache effects, and some operations like ArrayList.add are amortized O(1), so Big-O is the primary tool for reasoning about scale, but Rajesh still measures on real data for the final word.
Remember one sentence: Big-O names the growth rate ignoring constants, and the fastest win in banking is replacing an O(n squared) nested loop with an O(n) HashSet pass.
---