An algorithm processes an input of size 'n' by dividing it in half repeatedly until the size becomes 1. What is the most likely time complexity of this algorithm?
O(log n)
O(n log n)
O(n^2)
O(n)
Which asymptotic notation provides an upper bound on an algorithm's runtime, but the bound may not be tight?
Little-o (o)
Big-O (O)
Big Omega (Ω)
Big Theta (Θ)
You have two algorithms for a task: Algorithm A with Θ(n) complexity and Algorithm B with O(n^2) complexity. Which statement is ALWAYS true?
Algorithm A and Algorithm B have the same efficiency in terms of time complexity.
Algorithm B might be faster for very small input sizes, but Algorithm A will eventually be faster as input grows.
It's impossible to compare the efficiency of the algorithms without knowing the exact implementation details.
Algorithm A will be faster than Algorithm B for all input sizes.
Consider a binary search algorithm on a sorted array. In the worst-case scenario, how many comparisons are required to find a target element?
logâ‚‚(n) + 1
n/2
1
n
Which of the following scenarios typically leads to an algorithm with linear time complexity, O(n)?
Finding the smallest element in a max-heap.
Calculating the Fibonacci sequence recursively.
Traversing a binary tree.
Performing a linear search on a sorted array.
If an algorithm has a time complexity of Ω(n log n), what can you conclude about its best-case runtime?
It cannot be faster than an algorithm with O(log n) time complexity.
It will always be faster than an algorithm with O(n) time complexity.
It will always be slower than an algorithm with O(n^2) time complexity.
It will have a constant runtime regardless of input size.
Which of the following has a time complexity of O(n^2) in its worst-case scenario?
Bubble Sort
QuickSort
Merge Sort
Heap Sort
What is the time complexity of inserting an element at the beginning of a singly linked list?
O(1)
What is the time complexity of Dijkstra's algorithm for finding the shortest path in a graph with V vertices and E edges using an adjacency list and a priority queue?
O(V log E)
O(V + E)
O(V^2)
O(E log V)
The Floyd-Warshall algorithm is used to find the shortest path between:
All pairs of vertices in a graph
A vertex and all other vertices in a graph
None of the above
Two specified vertices in a graph