Kth Smallest Element Using Min Heap in DSA Javascript - Time & Space Complexity

Time Complexity: Kth Smallest Element Using Min Heap

O(n log n + k log n)

Understanding Time Complexity

We want to understand how the time needed to find the kth smallest element grows as the input size changes.

Specifically, how the operations scale when using a min heap to solve this problem.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function kthSmallest(arr, k) {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
  }
  return result;
}
    

This code builds a min heap from the array, then extracts the smallest element k times to find the kth smallest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting all elements into the min heap and extracting the minimum k times.
• How many times: Insert runs n times (for all elements), extractMin runs k times.

How Execution Grows With Input

Building the heap takes time proportional to the number of elements, and extracting k times adds more work.

Input Size (n)	Approx. Operations
10	About 10 insertions + k extractions, each operation costs a few steps.
100	About 100 insertions + k extractions, more steps but still manageable.
1000	About 1000 insertions + k extractions, operations grow but remain efficient.

Pattern observation: The total work grows roughly linearly with n for building, plus extra work proportional to k for extraction.

Final Time Complexity

Time Complexity: O(n log n + k log n)

This means the time grows mostly with n times log n for building the heap, plus k times log n for extracting elements.

Common Mistake

[X] Wrong: "Building the heap is just O(n) so total time is O(n + k)."

[OK] Correct: Building a heap by inserting elements one by one costs O(n log n), because each insertion takes log n time. So total time is more than just O(n).

Interview Connect

Understanding how heap operations add up helps you explain your solution clearly and shows you know how data structures affect performance.

Self-Check

"What if we used a max heap of size k instead of a min heap for all n elements? How would the time complexity change?"