Question

Consider functions Function_1 and Function_2 as follows. Let \(f_1(n)\) and \(f_2(n)\) be the number of times the statement \(x = x + 1\) executes in Function_1 and Function_2, respectively. Which statements are TRUE?

Function_1                          Function_2
while n>1 do                      for i = 1 to 100 * n do
  for i = 1 to n do                   x = x + 1;
    x = x + 1;                      end for
  end for
  n = floor(n/2);
end while

• A.
• B.
• C.
• D.

Hint:

Geometric halving patterns like \(n + n/2 + n/4 + \) sum to a constant multiple of \(n\). Whenever two functions are both \(\Theta(n)\), they are \(\Theta\) of each other and each is \(O\) of the other.

Answer 1

The Correct Option is A

Step 1 (Cost of Function_2): The loop runs exactly \(100n\) times, so \(f_2(n)=100n=\Theta(n)\).

Step 2 (Cost of Function_1): In each iteration of the while, the inner loop runs \(n\) times, then \(n\) is halved: \(n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \).
Hence \[ f_1(n)=n+\Big\lfloor\frac{n}{2}\Big\rfloor+\Big\lfloor\frac{n}{4}\Big\rfloor+s \le n+\frac{n}{2}+\frac{n}{4}+s = 2n, \] and also \(f_1(n)\ge n\).
Therefore \(f_1(n)=\Theta(n)\).

Step 3 (Compare \(f_1\) and \(f_2\)): Since both are \(\Theta(n)\), we have \(f_1(n)\in \Theta(f_2(n))\), which implies \(f_1(n)\in O(f_2(n))\).
Neither \(f_1(n)\in o(f_2(n))\) nor \(f_1(n)\in \omega(f_2(n))\) holds because their ratio tends to a positive constant (between \(1/100\) and \(2/100\)).

\[ \boxed{\text{True statements: (A) and (D).}} \]