Convert Sorted Array to Balanced BST in DSA Javascript - Time & Space Complexity

Time Complexity: Convert Sorted Array to Balanced BST

O(n log n)

Understanding Time Complexity

We want to know how the time needed to build a balanced binary search tree changes as the input array grows.

How does the number of steps grow when the array size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function sortedArrayToBST(nums) {
  if (nums.length === 0) return null;
  const mid = Math.floor(nums.length / 2);
  const root = { val: nums[mid], left: null, right: null };
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1, nums.length));
  return root;
}
    

This code builds a balanced binary search tree by picking the middle element as root and recursively doing the same for left and right parts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that split the array and create tree nodes.
• How many times: Each element is processed once as the middle element in some recursive call.
• Additional cost: Array slicing creates new arrays at each step, which takes time proportional to the slice size.

How Execution Grows With Input

Each recursive call splits the array roughly in half, but slicing copies parts of the array, adding extra work.

Input Size (n)	Approx. Operations
10	About 50 (due to slicing and recursion)
100	About 1000
1000	About 20000

Pattern observation: The work grows faster than just n because slicing copies arrays repeatedly, causing extra cost.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the input size because of splitting and copying arrays at each step.

Common Mistake

[X] Wrong: "The time complexity is O(n) because each element is visited once."

[OK] Correct: Although each element is chosen once, slicing arrays copies parts repeatedly, adding extra work that makes it slower than O(n).

Interview Connect

Understanding this helps you explain how recursion and data copying affect performance, a key skill in building efficient tree structures.

Self-Check

"What if we passed start and end indexes instead of slicing arrays? How would the time complexity change?"