Time and Space Complexity

Question 1

What is the time complexity of inserting into a balanced BST?

Answer 1

O(log n) for insertion, as the tree height is logarithmic in a balanced BST.

Question 2

What is the space complexity of a recursive algorithm?

Answer 2

O(h) where h is the recursion depth (stack frames).

Example: DFS on a tree has O(h) space, where h is tree height.

Question 3

When to use O(n) vs. O(log n) algorithms in C++?

Answer 3

Use O(log n) (e.g., binary search, balanced BST) for large datasets with sorted or structured data. Use O(n) (e.g., linear scan) for unsorted data or when simplicity is prioritized.