Performance analysis: time and space complexity, asymptotic notation and recurrence relations. - One Line Questions
1.
If an algorithm's time complexity is O(n^3), and the input size increases from 10 to 20, by what factor does the execution time increase? —
8
2.
What does the recurrence relation T(n) = T(n-1) + O(1) typically represent? —
An algorithm with linear time complexity
3.
Theta notation (Θ) provides: —
A tight bound on the growth rate
4.
Which of the following has the worst time complexity for searching? —
Unsorted Array
5.
Which notation is used to denote the tight bound of an algorithm's growth rate? —
Big Theta (Θ)
6.
Which of the following represents the tightest possible upper bound for the growth rate of a function? —
Big Theta (Θ)
7.
Which of the following represents the best-case time complexity? —
Big Omega (Ω)
8.
Which asymptotic notation is typically used to express the worst-case time complexity? —
Big O (O)
9.
Which asymptotic notation is used to describe the upper bound of growth rate? —
Big O (O)
10.
Which scenario best describes an algorithm with O(2^n) time complexity? —
Brute-force Traveling Salesperson Problem solution
11.
Which case of the Master Theorem applies when f(n) = Θ(n^(log_b a))? —
Case 2
12.
Consider a function that doubles its input size in each recursive call, and the work done at each step is constant: T(n) = T(n/2) + O(1). This is solved by which Master Theorem case? —
Case 1
13.
Which of the following is a characteristic of Little o notation (o)? —
It denotes an upper bound that is not tight.
14.
Consider an algorithm with a time complexity of O(n^2). If the input size doubles, how does the execution time approximately change? —
It quadruples
15.
If an algorithm has a time complexity of O(n log n), and the input size is multiplied by 16, how does the execution time change approximately? —
It increases by a factor of 16 * log(16)
16.
What does the recurrence T(n) = T(n/2) + O(1) represent? —
Logarithmic time complexity
17.
What is the time complexity of searching for an element in an unsorted array using linear search? —
O(n)
18.
What is the space complexity of a recursive function that has a maximum recursion depth of 'd' and each call uses constant space? —
O(d)
19.
What is the time complexity of deleting an element at the end of a singly linked list (without a tail pointer)? —
O(n)
20.
What is the space complexity of storing 'n' elements in a hash table? —
O(n)
21.
What is the space complexity of merge sort? —
O(n)
22.
What is the space complexity of quicksort (in-place implementation, ignoring recursion stack)? —
O(1)
23.
What is the time complexity of finding the minimum element in an unsorted array? —
O(n)
24.
What is the time complexity of inserting an element into a sorted array while maintaining the sorted order? —
O(n)
25.
What is the space complexity of a recursive function call stack if the maximum depth of recursion is 'n'? —
O(n)
26.
Which of the following is NOT an example of an asymptotic notation? —
O(n + k)
27.
What is the time complexity of accessing an element in an array by its index? —
O(1)
28.
What is the time complexity of binary search on a sorted array? —
O(log n)
29.
Consider a loop that iterates 'n' times, and inside the loop, an operation takes O(n) time. What is the overall time complexity? —
O(n^2)
30.
If T(n) = 2T(n/2) + O(n), what is the time complexity? —
O(n log n)
31.
What is the time complexity of inserting an element at the beginning of a singly linked list? —
O(1)
32.
What is the typical time complexity for inserting into a hash table? —
O(1) on average
33.
Consider the recurrence T(n) = T(n-1) + O(n). What is its solution? —
O(n^2)
34.
What is the time complexity of bubble sort in the worst case? —
O(n^2)
35.
What is the time complexity of merge sort in the worst case? —
O(n log n)
36.
What is the time complexity of quicksort in the average case? —
O(n log n)
37.
What is the time complexity of quicksort in the worst case? —
O(n^2)
38.
What is the time complexity of heap sort in the worst case? —
O(n log n)
39.
Which of the following describes an algorithm that performs a fixed number of operations regardless of the input size? —
O(1)
40.
What is the time complexity of adding two numbers? —
O(1)
41.
Consider the recurrence T(n) = 2T(n/2) + O(1). What is its solution? —
O(n)
42.
What is the lower bound of the time complexity of any comparison-based sorting algorithm? —
O(n log n)
43.
What is the space complexity of an algorithm that uses a fixed number of variables, regardless of input size? —
O(1)
44.
If T(n) = 4T(n/2) + n, what is the time complexity according to the Master Theorem? —
O(n^2)
45.
Consider the recurrence T(n) = 3T(n/3) + n. What is the time complexity? —
O(n log n)
46.
The Master Theorem is used to solve which type of problems? —
Recurrence relations of the form T(n) = aT(n/b) + f(n)
47.
What does Big O notation primarily describe? —
The upper bound of an algorithm's execution time or space usage
48.
What is the space complexity of an algorithm? —
The maximum memory required by the algorithm at any point during its execution
49.
What is the primary goal of performance analysis in algorithms? —
To determine the optimal algorithm for a given problem