Performance Analysis - time and space complexities, asymptotic notation, recurrence relations - One Line Questions
1.
What does 'Little o' (o) notation represent? —
A strict upper bound (function grows strictly slower)
2.
What does 'Little omega' (ω) notation represent? —
A strict lower bound (function grows strictly faster)
3.
Which of the following is an example of an algorithm with O(1) time complexity? —
Accessing an element in an array by its index.
4.
What does Big Theta (Θ) notation signify? —
A tight bound on the growth rate.
5.
Which of the following is NOT a standard asymptotic notation used in performance analysis? —
Big Sigma (Σ)
6.
Which asymptotic notation provides a lower bound on the growth rate of a function? —
Big Omega (Ω)
7.
Which asymptotic notation provides a tight bound (both upper and lower) on the growth rate of a function? —
Big Theta (Θ)
8.
Which asymptotic notation provides an upper bound on the growth rate of a function? —
Big O (O)
9.
Which of the following is an example of an algorithm with O(n log n) time complexity? —
Merge Sort
10.
The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(n^log_b a)? —
f(n) = O(n^(log_b a - ε)) for some ε > 0
11.
The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(f(n))? —
f(n) = Θ(n^(log_b a))
12.
The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(n^(log_b a))? —
f(n) = O(n^(log_b a + ε)) for some ε > 0
13.
What is the space complexity of a recursive function that has a maximum recursion depth of k? —
O(k)
14.
What is the space complexity of an algorithm that uses an auxiliary array of size n? —
O(n)
15.
What is the Big O complexity of an algorithm that iterates through a list of n elements once? —
O(n)
16.
What is the Big O complexity of linear search on an unsorted array of n elements? —
O(n)
17.
Consider the recurrence relation T(n) = 2T(n/2) + n. What is its solution using the Master Theorem (assuming n is a power of 2)? —
O(n log n)
18.
Which growth rate is faster: O(log n) or O(n)? —
O(n)
19.
Which growth rate is faster: O(n^2) or O(n log n)? —
O(n^2)
20.
If an algorithm's runtime is T(n) = 5n + 20, what is its Big O complexity? —
O(n)
21.
If an algorithm's runtime is T(n) = 2^n + n^3, what is its Big O complexity? —
O(2^n)
22.
What is the Big O complexity of an algorithm that iterates through a list of n elements using nested loops, where each loop runs n times? —
O(n^2)
23.
What is the Big O complexity of binary search on a sorted array of n elements? —
O(log n)
24.
Consider the following C code snippet: `for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { /* constant time operation */ } }`. What is its time complexity? —
O(n^2)
25.
Consider the following C code snippet: `int i = 1; while (i < n) { i *= 2; }`. What is its time complexity? —
O(log n)
26.
Consider the following C code snippet: `int i = n; while (i > 0) { i /= 2; }`. What is its time complexity? —
O(log n)
27.
What is the space complexity of an algorithm that sorts an array of n elements in-place (e.g., Heap Sort)? —
O(1)
28.
Consider the recurrence relation T(n) = T(n/2) + c. What is its solution? —
O(log n)
29.
Consider the recurrence relation T(n) = 4T(n/2) + n. What is its solution using the Master Theorem? —
O(n^2)
30.
Consider the recurrence relation T(n) = 2T(n/2) + n^2. What is its solution using the Master Theorem? —
O(n^2)
31.
If an algorithm's runtime is T(n) = 3n^2 + 5n + 10, what is its Big O complexity? —
O(n^2)
32.
If an algorithm's runtime is T(n) = 100, what is its Big O complexity? —
O(1)
33.
If an algorithm's runtime is T(n) = n log n + 5n, what is its Big O complexity? —
O(n log n)
34.
Which measure quantifies the amount of time an algorithm takes to run? —
Time complexity
35.
Which of the following is a typical base case for a recurrence relation? —
T(1) = c
36.
If T(n) is Θ(f(n)), which of the following is true? —
T(n) is O(f(n)) and T(n) is Ω(f(n))
37.
What does 'best-case' complexity refer to in algorithm analysis? —
The minimum time or space required for any input.
38.
What does 'average-case' complexity refer to in algorithm analysis? —
The expected time or space required over all possible inputs.
39.
What does 'worst-case' complexity refer to in algorithm analysis? —
The maximum time or space required for any input.
40.
What does T(n) = O(n^2) imply about the algorithm's runtime? —
The runtime is always less than or equal to c*n^2 for some constant c.
41.
What does T(n) = Ω(n^2) imply about the algorithm's runtime? —
The runtime is always greater than or equal to c*n^2 for some constant c.
42.
What does T(n) = Θ(n^2) imply about the algorithm's runtime? —
The runtime is always less than or equal to c1*n^2 and greater than or equal to c2*n^2 for some constants c1 and c2.
43.
Which measure quantifies the amount of memory an algorithm uses? —
Space complexity
44.
What is the primary use of recurrence relations in algorithm analysis? —
To describe and solve the time complexity of recursive algorithms.
45.
What is the primary goal of performance analysis in algorithms? —
To determine the efficiency of an algorithm in terms of time and space.
46.
If f(n) = n^2 and g(n) = n, then f(n) is Ω(g(n)). Is this statement true or false? —
True
47.
If f(n) = n and g(n) = n^2, then f(n) is O(g(n)). Is this statement true or false? —
True
48.
If f(n) = 2n + 5 and g(n) = n, then f(n) is Θ(g(n)). Is this statement true or false? —
False
49.
If f(n) = 3n^2 + 2n + 1 and g(n) = n^2, then f(n) is Θ(g(n)). Is this statement true or false? —
True