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

To solve the problem, we need to determine how many times the statement \( x = x + 1 \) executes in both Function_1 and Function_2.

Analysis of Function_1:

Function_1 is structured as follows:

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

Logic:

• The outer while loop continues as long as \( n \gt 1 \).
• The for loop runs from 1 to \( n \), executing \( n \) times.
• After each complete iteration of the for loop, the value of \( n \) is halved (integer division). Therefore, the sequence of \( n \) throughout the while loop may look like: \( n, \frac{n}{2}, \frac{n}{4}, \ldots \) until \( n \leq 1 \).

Calculation:

• If we let \( n = n_0 \), then the number of iterations for the while loop before terminating is approximately \( \log_2(n_0) \).
• The total executions of \( x = x + 1 \) will be the sum of a geometric progression: \( n_0 + \frac{n_0}{2} + \frac{n_0}{4} + \ldots \)
• This series sums to approximately \( 2 \times n_0 \).

Analysis of Function_2:

Function_2 is structured as follows:

for i = 1 to 100 * n do
  x = x + 1;
end for

Logic and Calculation:

• The for loop runs from 1 to \( 100 \times n \), which means it executes exactly \( 100 \times n \) times.

Conclusion:

• The number of executions of \( x = x + 1 \) in Function_1 is \( \approx 2n \).
• The number of executions of \( x = x + 1 \) in Function_2 is exactly \( 100n \).

Given these calculations, the statement which compares \( f_1(n) \) and \( f_2(n) \) would conclude that \( f_2(n) \) executes significantly more times than \( f_1(n) \) for large values of \( n \) since \( 100n \) is much larger than \( \approx 2n \).