JAVA RECURSION

Answer Key & Detailed Explanations

Each answer includes WHY it is correct and WHY the traps are wrong.

SECTION 1 — OUTPUT TRACING

Q1. What is the output of the following Java code?

Correct Answer: (A) 1 2 1 3 1 2 1
Explanation: f(3) calls f(2) first, then prints 3, then calls f(2) again. Each f(2) calls f(1) before printing,
then f(1) after. Full expansion:
f(1)→f(0), print 1, f(0) → prints: 1
f(2)→f(1), print 2, f(1) → prints: 1 2 1
f(3)→f(2), print 3, f(2) → prints: 1 2 1 3 1 2 1
The two recursive calls sandwich the print, mirroring output around each level. This produces a
palindrome-like output. Trap: people only trace one branch and miss the second recursive call after
the print.

Q2. What does the following Java code print?

Correct Answer: (A) 0
Explanation: x starts at 0. The call chain: f(3) increments x to 1, calls f(2). f(2) increments to 2, calls
f(1). f(1) increments to 3, calls f(0). f(0) increments to 4, n=0 so no more recursion, decrements back to
3. Returns to f(1): decrements to 2. Returns to f(2): decrements to 1. Returns to f(3): decrements to 0.
Final value: 0.

The increment/decrement perfectly cancel out. Trap: 95% of people answer 4 (the PEAK value)
instead of 0 (the FINAL value). The key insight is x++ happens before recursion and x-- happens after
return — they are perfectly symmetric.

Q3. What is the output of this Java code?

Correct Answer: (A) 1101
Explanation: go(13): calls go(6), then prints 13%2 = 1
go(6): calls go(3), then prints 6%2 = 0
go(3): calls go(1), then prints 3%2 = 1
go(1): calls go(0), then prints 1%2 = 1
go(0): n=0, returns immediately (nothing printed)

Print order (after calls return, bottom-up): 1, 1, 0, 1 → "1101"

This converts 13 to binary. 13 = 8+4+1 = 1101 in binary. Trap: people trace top-down and print in
reverse (1011), forgetting the print happens AFTER the recursive call returns.
Q4. What does this Java code print?
Correct Answer: (A) 4 2 1 0 0 1 2 4
Explanation: Trace each call — print happens BOTH before and after the recursive call:
f(4): prints 4, calls f(2), then prints 4
f(2): prints 2, calls f(1), then prints 2
f(1): prints 1, calls f(0), then prints 1
f(0): prints 0, returns (base case — no second print, return is immediate)

Unwinding: "4" "2" "1" "0" (base returns) "1" "2" "4"
Full output: 4 2 1 0 1 2 4

Wait — f(0) prints 0 then returns. There is NO second print after f(0). So: 4 2 1
0 0 1 2 4? No — f(0) prints once (before the return). f(1) prints 1, calls f(0)
which prints 0, returns, then f(1) prints 1. So: 4 2 1 0 0 1 2 4. The base case
returns before the second print in each caller, but f(0) itself prints once.
Full: 4 2 1 0 0 1 2 4.

Q5. What is the output?

Correct Answer: (B) 3 6
Explanation: The static field 'count' persists across ALL calls including separate invocations.

In Java, the + operator in println evaluates left-to-right. However, f(3) and

f(3) are TWO separate method calls:
First f(3): count goes 0→1→2→3, returns count = 3
Second f(3): count goes 3→4→5→6, returns count = 6

Output: "3 6"

Trap 1: Thinking it prints "3 3" — forgetting count persists between calls.
Trap 2: Thinking "6 6" — forgetting Java evaluates left-to-right.
Trap 3: In C, evaluation order is unspecified (right-to-left common), but in Java
println(f(3) + " " + f(3)) evaluates left-to-right guaranteed. Answer: 3 6.

SECTION 2 — COMPLEXITY & RECURRENCE TRAPS

Q6. What is the time complexity of this Java method?

Correct Answer: (A) O(n^log₂3) ≈ O(n^1.585)
Explanation: Recurrence: T(n) = 3T(n/2) + O(1)
Master Theorem: a=3, b=2, f(n)=O(1)=O(n⁰)
n^(log₂3) ≈ n^1.585

Since f(n)=O(1) is polynomially smaller than n^1.585, Case 1 applies:

 T(n) = Θ(n^(log₂3)) ≈ Θ(n^1.585)

Critical trap: f(n/2) appears 3 times so a=3. n halves each level so b=2. The
constant O(1) work per node means Case 1. Many people say O(3^n) thinking "3
recursive calls = 3^n" — this is wrong when the input shrinks (n/2 not n-1).
O(3^n) would apply if each call used f(n-1). With f(n/2), the depth is log₂n, so
total nodes = 3^(log₂n) = n^(log₂3).

Q7. What is the exact number of times "Java" is printed?

Correct Answer: (A) 15
Explanation: Let C(n) = number of prints from f(n).
C(0) = 0 (base case returns without printing)
C(n) = 2·C(n-1) + 1 (two recursive calls + one print)

Solving: C(n) = 2^n - 1

C(1) = 2·0 + 1 = 1
C(2) = 2·1 + 1 = 3
C(3) = 2·3 + 1 = 7
C(4) = 2·7 + 1 = 15

Answer: 15

Trap: People say 2^4 = 16, forgetting the base case contributes 0 prints. The -1
comes from f(0) nodes being "free" (they only return, never print). Total nodes
in binary tree of depth 4 = 31, but half are leaves that return without printing
→ 15 printing nodes.

Q8. Solve the recurrence: T(n) = 4T(n/2) + n²

Correct Answer: (A) O(n² log n)
Explanation: Master Theorem: a=4, b=2, f(n)=n²
n^(log_b a) = n^(log₂4) = n^2

Compare: f(n) = n² vs. n^(log_b a) = n²

They are EQUAL → Case 2 applies:
T(n) = Θ(n^(log_b a) · log n) = Θ(n² · log n)

This is the most commonly missed Master Theorem case.

Trap 1: "f(n) = n² = n^(log_b a) so it must just be O(n²)" — WRONG, Case 2
multiplies by log n.
Trap 2: Applying Case 3 because n² seems "large" — Case 3 requires n^(log₂4+ε) for some ε>0.
The log factor is the entire point of Case 2. Answer: O(n² log n).

Q9. What is the maximum call stack depth when running merge sort on an array of 1,048,576 (2²⁰)
elements in Java?
 Correct Answer: (A) 20
Explanation: Merge sort halves the array at each level. Stack depth = number of levels = log₂(n).
log₂(2²⁰) = 20

At any point during execution, the call stack contains one frame per level from the current position up
to the root. Maximum simultaneous frames = log₂(n) + 1 ≈ 21 (including the initial call).

This is ≈ 20 stack frames for 1 million elements — extremely manageable. Java's default stack
supports thousands of frames.

Trap: Many say n/2 = 524,288 thinking "the deepest recursive call processes 1 element, which is
524,288 levels deep." Wrong — each level HALVES the input, so depth is logarithmic, not linear. This
is the beauty of divide-and-conquer.

SECTION 3 — CALL STACK & STATE TRAPS

Q10. What is the output of the following Java code?

Correct Answer: (A) 5 4 3 2 1
Explanation: The recursive call f(i+1) happens BEFORE the print. So printing happens on the way
back up:
f(0)→f(1)→f(2)→f(3)→f(4)→f(5) [base case, returns]
f(4) resumes: prints arr[4]=5
f(3) resumes: prints arr[3]=4
f(2) resumes: prints arr[2]=3
f(1) resumes: prints arr[1]=2
f(0) resumes: prints arr[0]=1

Output: 5 4 3 2 1

Trap: People see the loop going 0→1→2→3→4 and print 1 2 3 4 5. They forget the
print is AFTER the recursive call (post-order), so execution is effectively
reversed.

Q11. How many total method calls (including the initial call) are made to compute fib(10) using
naive recursion?
Correct Answer: (A) 177
Explanation: Total calls C(n) follows the recurrence: C(n) = C(n-1) + C(n-2) + 1
With C(0)=1, C(1)=1 (just the base case call itself)

C(2) = 1+1+1 = 3
C(3) = 3+1+1 = 5
C(4) = 5+3+1 = 9
C(5) = 9+5+1 = 15
C(6) = 15+9+1 = 25
 C(7) = 25+15+1 = 41
C(8) = 41+25+1 = 67
C(9) = 67+41+1 = 109
C(10) = 109+67+1 = 177

Formula: C(n) = 2·fib(n+1) - 1. fib(11)=89, so 2·89-1=177.

Trap 1: Saying 55 (the RETURN VALUE of fib(10)).

Trap 2: Saying 89 (fib(11), off by the formula).
Trap 3: Saying 109 (C(9), one step behind).

Q12. What does this Java code output?

Correct Answer: (A) 1 2 4 8 16 5 10 3 6
Explanation: This traces the Collatz (3n+1) sequence, but PRINTS AFTER the recursive call (post-
order).

Collatz path from 6: 6→3→10→5→16→8→4→2→1 (base case)

Printing happens on the way BACK up the call stack:

f(1): prints 1 [base case]
f(2): prints 2
f(4): prints 4
f(8): prints 8
f(16): prints 16
f(5): prints 5
f(10): prints 10
f(3): prints 3
f(6): prints 6

Output: 1 2 4 8 16 5 10 3 6

Trap: Printing the Collatz sequence forward (top-down order) instead of

recognizing it prints bottom-up (return order). The path has 9 values → 9 numbers
printed.

SECTION 4 — TAIL RECURSION & JAVA SPECIFICS

Q13. Which version is tail-recursive in Java? (Note: Java does NOT perform TCO)
Correct Answer: (A) Version A is tail-recursive but STILL uses O(n) stack in Java (no
TCO)
Explanation: Version A IS structurally tail-recursive: the recursive call fact(n-1, acc*n) is the LAST
operation — multiplication is computed as an argument BEFORE the call. No pending work remains.

Version B is NOT tail-recursive: n * fact(n-1) means multiplication is pending after the call returns.
 HOWEVER — Java does NOT implement Tail Call Optimization (TCO). The JVM specification does
not mandate it, and the HotSpot JIT does not perform it (unlike Scala, Kotlin with @tailrec, or
Scheme).

So in Java: Version A is tail-recursive in structure but STILL creates n stack frames. Version B creates
n stack frames AND has pending operations. Both use O(n) stack space in practice.

Trap: Confusing structural tail recursion with actual stack optimization. In Java, tail recursion provides
zero automatic benefit — you must manually convert to a loop.

Q14. What is the issue with the following Java recursive string reverse?
Correct Answer: (A) O(n²) time due to String immutability; each + creates a new String
object
Explanation: The algorithm IS correct: reverse(s) = reverse(tail) + first_char.
reverse("abc") = reverse("bc") + 'a' = (reverse("c") + 'b') + 'a' = "cba" ✓

But the performance is terrible: Java Strings are IMMUTABLE. Every + creates a new String object by
copying all characters.

Cost analysis:
reverse("bc") + 'a' → copies 2+1 = 3 chars
reverse("c") + 'b' → copies 1+1 = 2 chars
Total character copies = 1 + 2 + ... + (n-1) = O(n²)

Also: O(n) stack depth.

Fix: Use [Link]() in an iterative approach → O(n).

Trap: Most people check the logic (which is correct) and miss the O(n²) string copying hidden inside
the + operator. This is a notorious Java performance trap.

SECTION 5 — TREE & STRUCTURAL RECURSION

Q15. What is the maximum recursion depth for in-order traversal of a BALANCED BST with
n=1,000,000 nodes in Java?
Correct Answer: (A) ~20 (O(log n))
Explanation: A balanced BST with n nodes has height ≈ log₂(n).
log₂(1,000,000) ≈ 19.93, so height ≈ 20.

In-order traversal recurses as deep as the tree height — one stack frame per level. So maximum
simultaneous stack frames ≈ 20.
 Java's default thread stack is 256KB–512KB, supporting thousands of frames. 20 frames is trivial.

Contrast: A degenerate BST (linked-list shaped, all right children) would be O(n)
= 1,000,000 frames deep → guaranteed StackOverflowError in Java.

Trap: Mixing up worst-case tree recursion (O(n) for skewed trees) with the specific question about
BALANCED trees (O(log n)). The word "balanced" is the critical qualifier.

Q16. For a skewed binary tree (all nodes have only right children) with n=100,000 nodes, calling a
recursive traversal in Java will:
Correct Answer: (A) Throw StackOverflowError — recursion depth = n = 100,000
Explanation: A skewed tree (all right children) is effectively a linked list. Recursive traversal from root
follows:
visit(root) → visit([Link]) → visit([Link]) → ... → n levels deep

Stack depth = n = 100,000 frames.

Java's default stack size:

-client JVM: ~512KB → ~8,000 frames
-server JVM: ~1MB → ~16,000 frames

100,000 frames far exceeds this → StackOverflowError.

This is why Java interview questions about BST recursion always specify "balanced." In production,
recursive tree algorithms on untrusted input must either:
1. Guarantee tree balance (AVL, Red-Black)
2. Use an explicit Stack<Node> instead of call stack
3. Use Morris traversal (O(1) space)

Trap: Thinking "Java handles recursion well" — the JVM does NOT have tail-call optimization or
automatic stack management.

Q17. What is the time complexity of building a binary tree from inorder and preorder traversals
WITH a HashMap for O(1) index lookup in Java?
Correct Answer: (A) O(n) — n nodes, O(1) work per node with HashMap
Explanation: WITHOUT HashMap: Finding root index in inorder array = O(n) per call × n calls = O(n²)

WITH HashMap (value → index):

Build map: O(n) preprocessing
Each recursive call: O(1) HashMap lookup + O(1) to compute left/right sizes
Total recursive calls: n (one per node)
Total: O(n)

This is a fundamental optimization interview question.

 Trap 1: Saying O(n log n) — this would require the recursion to have log n levels of n-work each (like
merge sort). Tree construction doesn't work this way.
Trap 2: Options C and D describe WITHOUT HashMap performance. The question explicitly says
WITH HashMap. Reading conditions carefully is the trap here.

SECTION 6 — DIVIDE & CONQUER

Q18. What is the subtle bug in this Java binary search?

Correct Answer: (A) Integer overflow: (lo + hi) overflows when both are near
Integer.MAX_VALUE
Explanation: (lo + hi) can overflow when both values are large positive integers near
Integer.MAX_VALUE.

Example: lo = 1_500_000_000, hi = 2_000_000_000

lo + hi = 3_500_000_000 which exceeds Integer.MAX_VALUE (2,147,483,647)
→ wraps to a negative number → mid is negative → ArrayIndexOutOfBoundsException

Fix: int mid = lo + (hi - lo) / 2;

This is Jon Bentley's famous bug — it existed in Java's own [Link]() for 9+ years
(discovered 2006, fixed 2007).

Base case lo > hi is CORRECT (handles empty range).

mid+1 and mid-1 are CORRECT (prevents infinite loop when lo==hi and no match).

Trap: This looks like textbook-correct binary search. The overflow is invisible unless you think about
extreme array indices (> 1 billion elements).

Q19. What is the total number of merge operations in merge sort on an array of 8 elements?
Correct Answer: (A) 7
Explanation: Merge sort on n=8 elements:
Level 1 (size 1→2): 4 merges (pairs: [1,2], [3,4], [5,6], [7,8])
Level 2 (size 2→4): 2 merges ([1-2,3-4] and [5-6,7-8])
Level 3 (size 4→8): 1 merge (final merge)
Total: 4 + 2 + 1 = 7

Formula: n - 1 = 8 - 1 = 7
This is a geometric series: n/2 + n/4 + ... + 1 = n - 1 for powers of 2.

Trap 1: Saying 8 (= n) — off by one, forgetting the series sums to n-1.

Trap 2: Saying 15 — counting ALL nodes in the recursion tree (including single-element "merges" of
leaves), but a 1-element array requires no merge.
Trap 3: Saying 4 — counting only the first level of merges.
SECTION 7 — MEMOIZATION & DYNAMIC PROGRAMMING

Q20. After memoizing Fibonacci in Java using a HashMap, the time complexity becomes O(n).
What is the SPACE complexity?
Correct Answer: (A) O(n) call stack + O(n) HashMap = O(n) total
Explanation: With top-down memoization:
HashMap stores n+1 entries → O(n) heap space
Call stack: fib(n) → fib(n-1) → fib(n-2) → ... → fib(0)
The FIRST call creates a chain n deep before memoization kicks in
→ O(n) stack frames simultaneously

Total space: O(n) stack + O(n) HashMap = O(n)

Trap 1: Thinking memoization eliminates the call stack — it doesn't. The first time fib(n) runs, it
recursively calls fib(n-1) which calls fib(n-2)... building up n frames before the base case returns.
Trap 2: O(log n) is wrong — the recursion is not divide-and-conquer here.
Trap 3: [Link]() is O(1) amortized, not O(n).

Note: Bottom-up DP (iterative) achieves O(1) space (only track last two values).

Q21. Why does the following memoization FAIL to reduce time complexity for Fibonacci in Java?
Correct Answer: (A) memo is a local variable — a new empty HashMap is created on
every call, so results are never shared
Explanation: The memo HashMap is declared as a LOCAL variable inside the method. Every single
call to fib() creates a BRAND NEW empty HashMap. When fib(n-1) is called, it gets its own new empty
memo. When fib(n-2) is called, same. No results are ever stored across calls.

This is identical to the naive O(φⁿ) implementation — just with HashMap overhead making it even
slower!

Fix: Declare memo as a static field OR pass it as a parameter OR use an instance variable:
static Map<Integer,Integer> memo = new HashMap<>();

Trap: The code looks "memoized" because it uses containsKey/put. The local variable bug is subtle —
the cache is always empty when checked because it's recreated each call. This is one of the most
common memoization implementation errors.

SECTION 8 — MUTUAL & INDIRECT RECURSION

Q22. What is the output of this Java mutually recursive code?

 Correct Answer: (A) 4 3 2 1 0
Explanation: Trace the execution:
f(4): prints 4, calls g(3)
g(3): prints 3, calls f(2)
f(2): prints 2, calls g(1)
g(1): prints 1, calls f(0)
f(0): prints 0, n=0 so NO recursive call

Output: 4 3 2 1 0

Each function simply prints n and passes n-1 to the other. The alternating
f→g→f→g creates a perfect countdown. No infinite recursion because n decrements
every call and both functions check n>0 before recursing.

Trap 1: Thinking each function prints twice (before and after) — prints happen only once, before the
recursive call.
Trap 2: Worrying about stack overflow — depth is only n+1 = 5 frames.
Trap 3: Saying "4 3 3 2 2 1 1 0 0" — forgetting each call goes to the other function, not back to itself.

SECTION 9 — TRICKY EDGE CASES

Q23. What is the result of calling f(0) in Java?

Correct Answer: (A) 1
Explanation: f(0): n=0, not < 0, so returns 1 + f(-1)
f(-1): n=-1, which IS < 0, returns 0
Result: 1 + 0 = 1

f(n) returns n+1 for all n ≥ 0.

Trap: Almost everyone checks "if (n < 0)" and assumes n=0 hits the base case — it doesn't! The base
case is n < 0, so n=0 recurses once more to n=-1. This is a classic base case boundary trap.

Many implementations accidentally write < 0 when they mean <= 0, changing
behavior for n=0 specifically. For this function: f(0)=1, f(1)=2, f(2)=3, etc.

Q24. What is the minimum number of base cases required for a correct recursive Fibonacci
implementation to avoid infinite recursion?
Correct Answer: (A) 2 — both fib(0) and fib(1) must be explicitly handled
Explanation: Fibonacci: fib(n) = fib(n-1) + fib(n-2)

With ONLY fib(0)=0:

fib(1) = fib(0) + fib(-1) = 0 + fib(-1)
fib(-1) = fib(-2) + fib(-3) → infinite recursion into negatives!
 With ONLY fib(1)=1:
fib(0) = fib(-1) + fib(-2) → infinite recursion!

You NEED both:

fib(0) = 0 (stops the n-2 chain)
fib(1) = 1 (stops the n-1 chain)

This is because each call reduces by BOTH 1 AND 2. Without anchoring both endpoints, one path
spirals negative.

Mathematically: this is a second-order linear recurrence — it requires 2 initial conditions, just like a
second-order differential equation. The number of base cases = the order of the recurrence.

Q25. What happens when you call f(7) in Java?

Correct Answer: (A) StackOverflowError — f(1) calls f(1) forever
Explanation: The first recursive call uses ⌈n/2⌉ (ceiling division = n/2 + n%2).

For n=1: ⌈1/2⌉ = 1. So f(1) calls f(1). INFINITE RECURSION!

Trace: f(7) → f(4) [since ⌈7/2⌉=4] → f(2) → f(1) → f(1) → f(1) → ... forever

The function never terminates for any odd n ≥ 1 because ⌈1/2⌉ = 1.

This is the most dangerous kind of bug — the recursion appears to be "dividing" toward a base case,
but ceiling division of 1 equals 1 (no progress). Contrast with floor division: ⌊1/2 ⌋ = 0, which WOULD
terminate.

Trap: People trace f(7)→f(4)→f(2) and think it will reach f(0). They don't notice
the ceiling division stalls at 1. The fix: change (n/2 + n%2) to just (n/2) for
floor division.

Q26. In recursive flood fill (4-connectivity) on an m×n image in Java, what is the worst-case
recursion depth?
Correct Answer: (A) m × n — a snake-path visits every pixel exactly once
Explanation: Flood fill explores pixels recursively. In the worst case, the fill region is a single snake-like
path that winds through every pixel — one long chain of connected pixels.

Example worst case (5×5 grid):

→ → → → ↓
↑ ← ← ← ↓
↓ → → → ↓
↓ ← ← ← ↓
→ → → → •
 This creates a recursion depth of m×n = 25. For a 1000×1000 image: 1,000,000
frames → instant StackOverflowError in Java.

This is why production flood fill uses an explicit Stack<Point> (iterative DFS) or BFS with a Queue —
never naive recursion.

Trap: People say m+n thinking of diagonal paths, or max(m,n) thinking rows are parallel. The snake
path specifically creates O(m×n) depth, not O(m+n).

SECTION 10 — ADVANCED RECURSION

Q27. What is the time complexity of computing ack(2, 3) using the Ackermann function, and what
does it return?
Correct Answer: (A) Returns 9; grows faster than any primitive recursive function
Explanation: Computing ack(2,3) step by step:
ack(2,3) = ack(1, ack(2,2))
ack(2,0) = ack(1,1) = ack(0,ack(1,0)) = ack(0,2) = 3
ack(2,1) = ack(1, ack(2,0)) = ack(1,3) = 5
ack(2,2) = ack(1, ack(2,1)) = ack(1,5) = 7
ack(2,3) = ack(1, 7) = 9

Pattern: ack(2,n) = 2n+3, so ack(2,3) = 9 ✓

The Ackermann function grows faster than any primitive recursive function. It is computable but NOT
primitive recursive — this is its significance in computability theory. For ack(4,4), the value has more
digits than atoms in the observable universe.

Trap: Confusing the return VALUE (9) with growth rate. The complexity "faster than primitive
recursive" is the conceptually important answer, not a standard Big-O class.

Q28. What is the time complexity of Karatsuba multiplication of two n-digit numbers?
Correct Answer: (A) O(n^1.585) — T(n) = 3T(n/2) + O(n)
Explanation: Karatsuba's key insight: multiply two n-digit numbers using only 3 multiplications of n/2-
digit numbers (instead of 4 in schoolbook).

Recurrence: T(n) = 3T(n/2) + O(n)

Master Theorem: a=3, b=2, f(n)=n
n^(log₂3) ≈ n^1.585 > n^1
Case 1 applies: T(n) = Θ(n^(log₂3)) ≈ Θ(n^1.585)

This is better than O(n²) schoolbook multiplication. The 3 vs 4 recursive multiplications makes the
exponent 1.585 vs 2.

Trap 1: O(n log n) is the Harvey-Hoeven 2019 algorithm using FFT — not Karatsuba.
 Trap 2: O(n log² n) is Toom-Cook variants — not Karatsuba.
Trap 3: O(n²) is schoolbook — exactly what Karatsuba improves upon.

Karatsuba is the same recurrence as Strassen's matrix multiplication (both use trick of reducing
recursive calls from k² to k^1.585 equivalent).

Q29. What is the average-case time complexity of recursive Quickselect (finding k-th smallest
element)?
Correct Answer: (A) O(n) — expected linear with random pivot
Explanation: Quickselect partitions the array and recurses on ONLY ONE side (the side containing the
k-th element).

With random pivot (expected to partition near middle):

T(n) = T(n/2) + O(n) on average
Unrolling: T(n) = O(n) + O(n/2) + O(n/4) + ... = O(n · (1 + 1/2 + 1/4 + ...)) =
O(2n) = O(n)

Key difference from quicksort:

Quicksort recurses on BOTH halves → T(n) = 2T(n/2) + O(n) = O(n log n)
Quickselect recurses on ONE half → T(n) = T(n/2) + O(n) = O(n)

Worst case (always bad pivot): T(n) = T(n-1) + O(n) = O(n²)

Guaranteed O(n) worst case: Median-of-Medians algorithm

Trap: Confusing average case O(n) with worst case O(n²), or with quicksort's O(n log n). The single-
side recursion is the critical distinction.

Q30. Which property of the Euclidean GCD algorithm guarantees O(log n) recursive calls?
Correct Answer: (A) Lame's theorem: inputs decrease by at least the Fibonacci ratio
each step
Explanation: Lame's theorem (1844) proves: the number of divisions in Euclidean GCD is at most 5
times the number of decimal digits of the SMALLER input.

The key: a % b < b/2 always. More precisely, inputs decrease at a rate governed by the Fibonacci
sequence (worst case: consecutive Fibonacci numbers). Since Fibonacci grows as φⁿ, inverting: after
k steps, inputs were at least φᵏ. Therefore k ≤ log_φ(n) = O(log n).

Trap 1: "Modulo halves the input" — this is sometimes true but NOT guaranteed.
Example: gcd(100, 99) → gcd(99, 1) → gcd(1, 0). Here 100%99=1, not 50.

Trap 2: "Reduces by at least 2" — completely wrong. gcd(1000000, 999999) reduces to gcd(999999,
1) in one step.

The Fibonacci-rate decrease is the precise guarantee, giving O(log n) calls, each taking O(d) time
where d = digits.
Q31. What does this Java function compute for f(12, 8)?
Correct Answer: (A) GCD(12, 8) = 4
Explanation: This is the subtraction-based Euclidean algorithm for GCD:
f(12, 8): a>b → f(4, 8)
f(4, 8): a<b → f(4, 4)
f(4, 4): a==b → returns 4

GCD(12, 8) = 4 ✓

This is the original Euclidean algorithm (300 BC) using subtraction instead of modulo. It's
mathematically equivalent to the modulo version but slower for large inputs with disparate values (e.g.,
GCD(1000000, 1) takes 1,000,000 recursive calls vs. 1 step with modulo).

Both versions compute GCD based on the property: GCD(a,b) = GCD(a-b, b) when a>b.

Trap: The function correctly returns 4, but returning 4 = a-b might make people think it computes
subtraction. The equality check (a==b) and self-referential structure are the giveaway that this is GCD.

Q32. What does this Java recursive function compute?

Correct Answer: (A) 42 — it computes a × b via Russian Peasant multiplication
Explanation: This is Russian Peasant (binary) multiplication: a × b

Trace f(6, 7):

f(6, 7): 6 even → f(3, 14)
f(3, 14): 3 odd → f(1, 28) + 14
f(1, 28): 1 odd → f(0, 56) + 28
f(0, 56): a=0, returns 0
Unwind: 0 + 28 = 28
28 + 14 = 42
Result: 42 = 6 × 7 ✓

Algorithm: uses binary representation of a:

6 = 110 in binary
When bit is 1, add current b (14, 28 contributions)
14 + 28 = 42

This is how CPUs implement integer multiplication using bit shifts and additions.

Trap: The function signature f(a, b) looks like it might compute a+b or a-b. The
doubling of b (b+b) and halving of a (a/2) are the Russian Peasant telltale
signs. Many confuse it with GCD or power functions.