1.3.1 Best, worst and average case; space complexity and recursion depth; amortised cost

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

T(n) = 2T(√n) + 1? from Lesson 1.2.4
T(n) = 2T(n/2) + n log n? from Lesson 1.2.3
Θ of for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++)? from Lesson 1.1.3

1 · The Hook

🎣

"Quicksort is O(n²)" and "quicksort is O(n log n)" are both said, and both are right: about different inputs. A complexity statement must say which case it measures. GATE also asks about memory (space) and about operations that are usually cheap but occasionally expensive.

2 · Predict First

🤔

Linear search looks for x in an array of n distinct elements; x is present and equally likely to be at any position. How many comparisons on average?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Position i costs i comparisons: (1 + 2 + … + n)/n = (n + 1)/2.

Best, worst and average case

For a fixed input size n, different inputs take different times.

Worst case: the maximum over all inputs of size n. GATE's default ("time complexity" means worst case unless stated).
Best case: the minimum.
Average case: the expected time over a stated distribution of inputs.

Linear search (x present, uniform position): best 1, worst n, average (n + 1)/2. If x may be absent: worst n (unsuccessful search).

Space complexity

Auxiliary space: extra memory beyond the input.
In-place: O(1) (or O(log n)) auxiliary space.
Recursion uses stack space: (maximum recursion depth) × (frame size). Recursive binary search: depth log n → O(log n) space; a T(n − 1) recursion: depth n → O(n) space.
Merge sort: Θ(n) auxiliary array; heapsort: O(1).

Amortised cost

Some operations are expensive rarely. Amortised cost = total cost of a sequence ÷ number of operations.

Dynamic array (doubling): when full, copy everything into an array twice as big. n appends cost n writes + copies 1 + 2 + 4 + … < 2n → total < 3n → O(1) amortised per append, though one append can cost Θ(n).
Stack with multipop: each element is pushed once and popped at most once → n operations cost O(n) total.

4 · Visual

Dynamic array doubling: copies at sizes 1, 2, 4, 8, ... 
append #:  1  2  3  4  5  6  7  8  9 ...
copies  :  0  1  2  0  4  0  0  0  8      total copies for n appends < 2n

Algorithm	Best	Worst	Average
Linear search (x present)	1	n	(n + 1)/2
Binary search	1	⌊log n⌋ + 1	≈ log n
Insertion sort	n − 1 comparisons	n(n − 1)/2	≈ n²/4

5 · Worked Examples

Example 1 Easy

A recursive function calls itself on n − 1 until n = 0, using a constant-size frame. Space?

Solution

Depth n + 1 → Θ(n) stack space.

Example 2 Medium

A dynamic array starts with capacity 1 and doubles when full. How many element copies happen during 100 appends?

Solution

Copies when growing from 1, 2, 4, 8, 16, 32, 64: 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127.

Example 3 GATE

Linear search for x in n = 9 distinct elements; x is absent with probability 1/2, otherwise equally likely at any position. Expected comparisons?

Solution

Absent: 9. Present: (9 + 1)/2 = 5. Expected = 0.5 × 9 + 0.5 × 5 = 7.

6 · GATE Traps

⚠️

"Time complexity" in GATE means worst case unless stated.
Recursion costs stack space even if no arrays are allocated.
Amortised O(1) does not mean every operation is O(1).
Average case needs a probability distribution.

7 · Memory Hook

🧠

"Worst is the default; recursion depth is space; spread the rare cost."

8 · Connect the Dots

Phase 1 is complete: notation, loops, recurrences, cases and space. Phase 2 puts it to work on the first syllabus topics: searching and hashing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markAverage search

Linear search in 20 distinct elements, x present and equally likely anywhere. Average comparisons?

Numerical answer: ________

Q2NAT2 marksDoubling copies

A dynamic array starts at capacity 1 and doubles when full. How many element copies during 1,000 appends?

Numerical answer: ________

Q3MCQ1 markRecursion space

Recursive binary search on n elements uses how much stack space?

(A) O(n log n)
(B) O(log n)
(C) O(1)
(D) O(n)

Q4MSQ2 marksFacts

Which are true?

(A) In GATE, "time complexity" without qualification means worst case.
(B) An in-place algorithm needs Θ(n) auxiliary space.
(C) Average-case analysis needs an assumed input distribution.
(D) Amortised O(1) per operation allows an individual operation to cost Θ(n).

Q5NAT2 marksExpected comparisons

Linear search over 11 distinct elements; x is absent with probability 0.4, otherwise uniform over positions. Expected comparisons?

Numerical answer: ________

10 · Rule Card

Worst (default), best, average (needs a distribution).
Linear search: 1 / n / (n+1)/2.
Space: auxiliary memory + recursion depth × frame; in-place = O(1).
Amortised = total ÷ operations; doubling array O(1) amortised (copies < 2n).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

worst, best and average caseexpected costauxiliary spacein-place algorithmrecursion stack spaceamortised costdynamic array doublingmultipop stack

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

Θ(log n).
Θ(n log² n).
Θ(n).