Time and Space Analysis of Algorithms

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Time and Space Analysis: comparing algorithms without running them

The single most foundational skill in this entire subject — everything else builds on top of this.

Before comparing two algorithms by actually running them (which depends on hardware, compiler, mood of the CPU), computer scientists needed a hardware-independent way to describe "how much work does this actually do as input grows?" That's exactly what Big-O gives you.

📈 Big-O, Omega, Theta

Big-O (O)Upper bound — the WORST case growth rate. "This algorithm never does worse than this."

Omega (Ω)Lower bound — the BEST case growth rate. "This algorithm never does better than this."

Theta (Θ)Tight bound — used when best and worst case grow at the SAME rate, giving an exact characterization.

Common growth rates, smallest to largest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) Example: for an array of 1000 elements — O(log n) ≈ 10 operations. O(n) = 1000. O(n²) = 1,000,000. That gap is exactly why algorithm choice matters enormously as data grows.

💡 Practice determining the Big-O of small code snippets (nested loops = O(n²), single loop = O(n), loop that halves each time = O(log n)) — this pattern recognition is tested constantly across this entire subject.

Why Big-O is the one that gets used

All three notations are defined correctly above, yet almost every complexity claim you meet is Big-O. There is a reason, and it is not laziness.

An upper bound is a guarantee. "This never does worse than n log n" is something you can build a system on. A lower bound tells you the algorithm is at least this slow sometimes, which is rarely what you need to know when deciding whether it will meet a deadline.

💡 Theta (Θ) is the most precise of the three, because it bounds from both sides — but it can only be stated when the upper and lower bounds match. For quicksort they do not: O(n²) worst case against Ω(n log n) best, so no single Θ describes it. That is exactly when Big-O alone is quoted.

The confusion the notation invites

Best case and lower bound are not the same thing, and treating them as synonyms is a standard exam trap.

⚠️ Two independent axes

CaseWhich INPUT you are considering — best, average or worst. A property of the data.

BoundWhich side you are bounding from — O above, Ω below, Θ both. A property of the mathematics.

They combine freely. It is entirely legitimate to state the Big-O of the best case, or the Omega of the worst case. Insertion sort is O(n) in the best case and O(n²) in the worst; both are upper bounds, on different inputs.

💡 So "insertion sort is Ω(n)" and "insertion sort's best case is O(n)" say different things, and a question asking for one will not accept the other. Name the case and the bound separately and the ambiguity disappears.

What the notation deliberately discards

Constants and lower-order terms are dropped, so 3n² + 500n + 2000 is simply O(n²). That is a feature — it makes the comparison hardware-independent — but it means Big-O says nothing about which algorithm is faster on any particular input size.

An O(n²) algorithm with small constants routinely beats an O(n log n) one on small inputs, which is why real sort implementations switch to insertion sort on small partitions. Big-O describes how cost grows, not what it is.

Syllabus points

Big-O, Omega (Ω), Theta (Θ) notations
Analyzing time & space complexity

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.