Consider functions Function_1 and Function_2 expressed in pseudocode as…
2023
Consider functions Function_1 and Function_2 expressed in pseudocode as follows:
Function_1
while n > 1 do
for i = 1 to n do
x = x + 1;
end for
n = \(n = \lfloor {n} / {2} \rfloor \)
end while
Function_2
for i = 1 to 100 ∗ n do
x = x + 1;
end for
Let \(f_1(n)\) and \(f_2(n)\) denote the number of times the statement “x = x + 1” is executed in Function_1 and Function_2, respectively. Which of the following statements is/are TRUE?
- A.
\(f_1(n) ∈ Θ(f_2(n))\) - B.
\(f_1(n) ∈ o(f_2(n))\) - C.
\(f_1(n) ∈ ω(f_2(n))\) - D.
\(f_1(n) ∈ O(n)\)
Attempted by 118 students.
Show answer & explanation
Correct answer: A, D
Key idea: compute the total number of increments in Function_1 and compare with Function_2.
Analyze f1(n): f1(n) = n + floor(n/2) + floor(n/4) + ... . This is bounded above by n + n/2 + n/4 + ... < 2n, so f1(n) ∈ O(n).
Also f1(n) ≥ n (the first term), so f1(n) ∈ Ω(n). Combining Ω(n) and O(n) gives f1(n) ∈ Θ(n).
Analyze f2(n): f2(n) = 100n, so f2(n) ∈ Θ(n).
Conclusion: Since both f1(n) and f2(n) are Θ(n), the statement f1(n) ∈ Θ(f2(n)) is true. Also f1(n) ∈ O(n) is true. The little-o and ω statements are false because the ratio f1(n)/f2(n) approaches a nonzero constant rather than 0 or ∞.