B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 1 — Questions and Answers
Question 1: What does O(n log n) time complexity indicate about an algorithm?
- The algorithm runs in constant time
- The algorithm's runtime grows linearly
- The algorithm's runtime grows proportionally to n multiplied by the logarithm of n (Correct answer)
- The algorithm runs in polynomial time
Correct answer: The algorithm's runtime grows proportionally to n multiplied by the logarithm of n
O(n log n) means the running time scales with n × log(n), typical of efficient sorting algorithms like merge sort and heap sort.
Question 2: Which sorting algorithm has the best worst-case time complexity?
- Quick Sort
- Bubble Sort
- Merge Sort (Correct answer)
- Insertion Sort
Correct answer: Merge Sort
Merge Sort guarantees O(n log n) in the worst case by always dividing the array in half and merging sorted halves, unlike Quick Sort which degrades to O(n²).
Question 3: What data structure does Depth-First Search (DFS) use internally?
- Queue
- Stack (Correct answer)
- Heap
- Hash table
Correct answer: Stack
DFS uses a stack (either explicitly or via the call stack in recursion) to explore as deep as possible before backtracking.
Question 4: Which algorithmic paradigm does dynamic programming primarily rely on?
- Greedy choice at each step
- Divide-and-conquer without storing subproblem results
- Memoization or tabulation of overlapping subproblems (Correct answer)
- Random sampling and approximation
Correct answer: Memoization or tabulation of overlapping subproblems
Dynamic programming solves problems by breaking them into overlapping subproblems and storing results (memoization or tabulation) to avoid redundant computation.
Question 5: What is the time complexity of binary search on a sorted array of n elements?
- O(n)
- O(n²)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
Binary search halves the search space with each comparison, giving O(log n) time complexity on a sorted array.
Question 6: Which graph algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edges?
- Bellman-Ford
- Dijkstra's Algorithm (Correct answer)
- Floyd-Warshall
- Prim's Algorithm
Correct answer: Dijkstra's Algorithm
Dijkstra's algorithm uses a priority queue to greedily select the nearest unvisited vertex and compute shortest paths from a source to all other vertices, provided edge weights are non-negative.
B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 1
What does O(n log n) time complexity indicate about an algorithm?