Time & Space Complexity (Big-O) Interview Questions Hindi mein

Time & Space Complexity (Big-O) कोर्स के 25 सवाल, हर सवाल के सही जवाब और explanation के साथ। जवाब देखने से पहले ख़ुद सोचें।

Why We Analyse Algorithms

1. What does complexity analysis primarily describe?

  1. How the work grows as the input size grows
  2. The exact running time in seconds
  3. The number of lines of code
  4. The programming language used
जवाब देखें

जवाब: How the work grows as the input size grows

Complexity describes growth as a function of n, independent of machine details.

पाठ: Measuring Algorithms Without a Stopwatch

2. For linear search on an array of n elements, what is the worst-case number of comparisons?

  1. 1
  2. log n
  3. n²
  4. n
जवाब देखें

जवाब: n

In the worst case every element is compared once, giving n comparisons.

पाठ: Counting Operations and Best, Worst and Average Cases

3. Which growth rate is the smallest for large n?

  1. O(n)
  2. O(n log n)
  3. O(log n)
  4. O(√n)
जवाब देखें

जवाब: O(log n)

Logarithmic growth is slower than any polynomial power of n, including √n.

पाठ: The Common Growth Rates

Asymptotic Notation

4. Which statement is true by the definition of Big-O?

  1. 2n + 100 is O(1)
  2. n³ is O(n²)
  3. 7n² + n is O(n²)
  4. n log n is O(n)
जवाब देखें

जवाब: 7n² + n is O(n²)

Constants and lower-order terms are absorbed; the n² term dominates.

पाठ: Big-O: The Formal Definition

5. What does f(n) = Θ(g(n)) mean?

  1. f grows strictly slower than g
  2. f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g
  3. f is always smaller than g
  4. f and g are equal for all n
जवाब देखें

जवाब: f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g

Theta is a tight bound: f is bounded above and below by constant multiples of g.

पाठ: Big-Omega, Big-Theta and Little-o

6. A function loops over a list of n items and, inside the loop, does a binary search on a sorted array of size m. What is its complexity?

  1. O(n log m)
  2. O(n + m)
  3. O(n²)
  4. O(log n)
जवाब देखें

जवाब: O(n log m)

n iterations each costing O(log m) multiply to O(n log m).

पाठ: Rules for Simplifying Complexity

Analysing Loops

7. What is the complexity of `for i in range(n): for j in range(i, n): work()` with constant-time work?

  1. O(n²)
  2. O(n)
  3. O(n log n)
  4. O(n³)
जवाब देखें

जवाब: O(n²)

The inner loop runs n + (n−1) + … + 1 = n(n+1)/2 times in total, which is O(n²).

पाठ: Single, Nested and Dependent Loops

8. How many iterations does `i = n; while i > 1: i = i // 2` perform, roughly?

  1. n
  2. n / 2
  3. √n
  4. log₂ n
जवाब देखें

जवाब: log₂ n

Halving n repeatedly reaches 1 after about log₂ n steps.

पाठ: Logarithmic and Square-Root Loops

9. In a sliding-window algorithm, the right pointer advances n times and the left pointer advances at most n times in total. What is the overall complexity?

  1. O(n²)
  2. O(n log n)
  3. O(n)
  4. O(log n)
जवाब देखें

जवाब: O(n)

Total pointer movement is at most 2n, so the work is linear.

पाठ: Tricky Loop Patterns

Analysing Recursion

10. Which recurrence describes binary search?

  1. T(n) = 2T(n/2) + O(n)
  2. T(n) = T(n − 1) + O(n)
  3. T(n) = T(n/2) + O(1)
  4. T(n) = 2T(n − 1) + O(1)
जवाब देखें

जवाब: T(n) = T(n/2) + O(1)

Binary search does constant work and recurses on one half of the input.

पाठ: Writing Recurrence Relations

11. Why is naive recursive Fibonacci exponential?

  1. It uses a loop inside the recursion
  2. It recomputes the same subproblems many times, with the call tree branching twice at each level
  3. Python recursion is slow
  4. It stores every result in memory
जवाब देखें

जवाब: It recomputes the same subproblems many times, with the call tree branching twice at each level

Overlapping subproblems are recomputed, so the number of calls grows exponentially.

पाठ: Recursion Trees and Exponential Recursion

12. Using the master theorem, what is T(n) = 4T(n/2) + n?

  1. Θ(n²)
  2. Θ(n)
  3. Θ(n log n)
  4. Θ(n² log n)
जवाब देखें

जवाब: Θ(n²)

log₂ 4 = 2, so n^(log_b a) = n², which dominates f(n) = n: case 1 gives Θ(n²).

पाठ: The Master Theorem

Space Complexity

13. What is the auxiliary space of reversing an array in place by swapping elements from both ends?

  1. O(1)
  2. O(n)
  3. O(log n)
  4. O(n²)
जवाब देखें

जवाब: O(1)

Only a constant number of index variables are used, regardless of n.

पाठ: Measuring Memory Use

14. What is the stack space used by a recursive function that recurses on n − 1 until reaching 0?

  1. O(1)
  2. O(log n)
  3. O(n²)
  4. O(n)
जवाब देखें

जवाब: O(n)

The recursion is n levels deep, so n frames exist at the deepest point.

पाठ: Recursion and the Call Stack

15. Prefix sums answer each range-sum query in O(1). What do they cost?

  1. Nothing
  2. O(n²) space
  3. O(n) preprocessing time and O(n) extra space
  4. O(log n) per query
जवाब देखें

जवाब: O(n) preprocessing time and O(n) extra space

Building the prefix array takes linear time and memory, paid once.

पाठ: Time-Space Trade-offs

Complexity of Data Structure Operations

16. What is the amortised cost of appending to a dynamic array that doubles its capacity when full?

  1. O(n)
  2. O(log n)
  3. O(1)
  4. O(n²)
जवाब देखें

जवाब: O(1)

Occasional O(n) copies average out to a constant per append because capacity grows geometrically.

पाठ: Arrays, Dynamic Arrays and Linked Lists

17. You need to repeatedly extract the smallest element while inserting new ones. Which structure fits best?

  1. Hash table
  2. Binary heap (priority queue)
  3. Unsorted array
  4. Linked list
जवाब देखें

जवाब: Binary heap (priority queue)

Heaps give O(log n) insert and remove-min with O(1) access to the minimum.

पाठ: Hash Tables, Trees and Heaps

18. What is the cost of `x in my_list` for a Python list of n elements?

  1. O(n)
  2. O(1)
  3. O(log n)
  4. O(n log n)
जवाब देखें

जवाब: O(n)

Membership in a list is a linear scan; use a set for average O(1) membership tests.

पाठ: Library Call Costs in Practice

Amortised Analysis, Sorting Bounds and Complexity Classes

19. Why is appending to a doubling dynamic array amortised O(1) even though some appends cost O(n)?

  1. The total copying cost over n appends is less than about n, so the average per append is constant
  2. Resizes never happen
  3. Copying is free in modern hardware
  4. Amortised means best case
जवाब देखें

जवाब: The total copying cost over n appends is less than about n, so the average per append is constant

Geometric growth makes the sum of all copies linear in n.

पाठ: Amortised Analysis

20. Why can counting sort run faster than Ω(n log n)?

  1. It uses better comparisons
  2. It only works on sorted input
  3. It ignores half the elements
  4. It is not comparison-based; it uses the integer values directly within a known range
जवाब देखें

जवाब: It is not comparison-based; it uses the integer values directly within a known range

The lower bound applies only to comparison sorts; counting sort indexes by key value.

पाठ: Sorting Complexities and the Lower Bound

21. Why is the O(n · W) knapsack algorithm called pseudo-polynomial?

  1. It runs in O(n) time
  2. It only approximates the answer
  3. Its running time is polynomial in the value W, but exponential in the number of bits used to represent W
  4. It requires quantum computers
जवाब देखें

जवाब: Its running time is polynomial in the value W, but exponential in the number of bits used to represent W

Input size counts the digits of W, and W can be exponentially large in that digit count.

पाठ: P, NP and Intractable Problems

Applying Complexity in Practice and Revision

22. What does the hash-map solution to two-sum trade to achieve O(n) time?

  1. Correctness
  2. Sorting stability
  3. O(n) extra space for the map
  4. Recursion depth
जवाब देखें

जवाब: O(n) extra space for the map

Storing seen values in a hash map uses linear extra memory to avoid the inner loop.

पाठ: From Brute Force to Efficient Solutions

23. A problem has n ≤ 200,000 and a one-second limit. Which complexity is most likely expected?

  1. O(n³)
  2. O(n log n)
  3. O(2ⁿ)
  4. O(n!)
जवाब देखें

जवाब: O(n log n)

With n around 2 × 10⁵, O(n²) is about 4 × 10¹⁰ operations, too many; O(n log n) fits easily.

पाठ: Reading Constraints to Pick an Approach

24. Why might an O(n log n) algorithm beat an O(n) algorithm in practice for realistic input sizes?

  1. Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference
  2. Big-O is always wrong
  3. O(n log n) is always faster
  4. log n is negative for large n
जवाब देखें

जवाब: Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference

Asymptotic notation hides constants and hardware effects that dominate for moderate n.

पाठ: Pitfalls and Real-World Performance

25. What is the solution of T(n) = T(n/2) + n?

  1. Θ(log n)
  2. Θ(n log n)
  3. Θ(n²)
  4. Θ(n)
जवाब देखें

जवाब: Θ(n)

n + n/2 + n/4 + … < 2n, so the root's linear work dominates: Θ(n) (master theorem case 3).

पाठ: Revision and Interview Questions

← कोर्स पर वापस जाएँ