Epic Skills Assessment Algorithmic Problem Solving 2 — Questions and Answers
Question 1: What is the time complexity of finding an element in a balanced binary search tree?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(1)
Correct answer: O(log n)
A balanced BST halves the search space at each level, yielding O(log n) lookup time.
Question 2: Which technique solves a problem by breaking it into overlapping subproblems and storing results to avoid redundant computation?
- Greedy algorithm
- Divide and conquer
- Dynamic programming (Correct answer)
- Backtracking
Correct answer: Dynamic programming
Dynamic programming stores subproblem solutions (memoization or tabulation) to avoid recomputing them.
Question 3: In a graph with V vertices and E edges, what is the space complexity of an adjacency list representation?
- O(V²)
- O(E)
- O(V + E) (Correct answer)
- O(V × E)
Correct answer: O(V + E)
An adjacency list stores each vertex once and each edge once (or twice for undirected), giving O(V + E).
Question 4: Which sorting algorithm has the best average-case time complexity?
- Bubble sort
- Insertion sort
- Merge sort (Correct answer)
- Selection sort
Correct answer: Merge sort
Merge sort guarantees O(n log n) average and worst case, outperforming the O(n²) algorithms.
Question 5: What does it mean for an algorithm to be 'in-place'?
- It runs in constant time
- It uses O(1) extra memory beyond the input (Correct answer)
- It never modifies the input
- It always produces a stable sort
Correct answer: It uses O(1) extra memory beyond the input
An in-place algorithm requires only a constant amount of auxiliary space regardless of input size.
Question 6: Which data structure is best suited for implementing a priority queue efficiently?
- Linked list
- Stack
- Binary heap (Correct answer)
- Hash table
Correct answer: Binary heap
A binary heap supports insert and extract-min/max in O(log n), making it the standard priority queue implementation.
Question 7: What is the worst-case time complexity of quicksort?
- O(n log n)
- O(n)
- O(n²) (Correct answer)
- O(log n)
Correct answer: O(n²)
Quicksort degrades to O(n²) when the pivot is always the smallest or largest element (e.g., already-sorted input with a naive pivot).
Epic Skills Assessment Algorithmic Problem Solving 2
What is the time complexity of finding an element in a balanced binary search tree?