Which of the following is correct order of increasing time complexity of algorithms A. Tower of Hanoi with n disk. B. Binary search given n sorted numbers. C. Heap sort given n numbers at the worst case. D. Addition of two n x n matrices. Choose the correct answer from the options given below:
Algorithm Time Complexities Analysis
To determine the correct order of increasing time complexity, we need to find the Big O notation for each algorithm:
- B. Binary Search: Dividing the search space in half repeatedly leads to a logarithmic time complexity.
Complexity: $O(\log n)$ - C. Heap Sort (Worst Case): Building the heap takes $O(n)$, and extracting n elements takes $O(n \log n)$.
Complexity: $O(n \log n)$ - D. Matrix Addition (n x n): Adding two $n \times n$ matrices requires performing $n^2$ additions.
Complexity: $O(n^2)$ - A. Tower of Hanoi (n disks): The number of moves follows the recurrence relation $T(n) = 2T(n-1) + 1$, which results in exponential growth.
Complexity: $O(2^n)$
Ordering Complexities
Arranging these complexities in increasing order:
- $O(\log n)$ (Binary Search - B)
- $O(n \log n)$ (Heap Sort - C)
- $O(n^2)$ (Matrix Addition - D)
- $O(2^n)$ (Tower of Hanoi - A)
Therefore, the correct sequence is B, C, D, A.
Important Questions from Asymptotic Worst Case Time and Time Complexity
Arrange the following in ascending order of their average case complexity.
Selection-sort, Quick-sort, Linear search, Binary search
- What is the average case time complexity of merge sort?
Arrange the following algorithms from the most efficient to least efficient based on their time complexity.
A. Kruskal's Algorithm
B. Breadth first search Algorithm
C. Bellman-Ford Algorithm
D. Dijkstra's Algorithm
E. Edmonds-Karp Algorithm.
Choose the correct answer from the options given below:
