Consider functions $\textbf{Function\_1}$ and $\textbf{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/2⌋; end whileFunction_2 for i = 1 to 100 * n do x = x + 1; end forLet $f_1(n)$ and $f_2(n)$ denote the number of times the statement “$x = x + 1$” is executed in $\textbf{Function\_1}$ and $\textbf{Function\_2}$, respectively. Which of the following statements is/are TRUE?

Let us compute the exact number of times the statement $x = x + 1$ is executed in both functions:

1. For Function_1:

   • In the first iteration of the while loop, the inner for loop executes $n$ times.

   • In the second iteration, $n$ becomes $\lfloor n/2 \rfloor$, so the inner loop executes $\lfloor n/2 \rfloor$ times.

   • This continues halving $n$ until $n \le 1$.

   • Thus, the total number of executions $f_1(n)$ is:

     $$f_1(n) = n + \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + \dots + 2$$

   • Using the properties of a geometric series:

     $$n \le f_1(n) < n \sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^k = 2n$$

   • Hence, $f_1(n) = \Theta(n)$ and $f_1(n) = O(n)$.

2. For Function_2:

   • The for loop runs directly from $1$ to $100 \times n$.

   • Thus, $f_2(n) = 100n = \Theta(n)$.

3. Evaluating the options:

   • Option (A): Since $f_1(n) = \Theta(n)$ and $f_2(n) = \Theta(n)$, we have $f_1(n) \in \Theta(f_2(n))$. Hence, (A) is TRUE.

   • Option (B): $\lim_{n \to \infty} \frac{f_1(n)}{f_2(n)} = \lim_{n \to \infty} \frac{\Theta(n)}{100n} \neq 0$. Therefore, $f_1(n) \notin o(f_2(n))$. Hence, (B) is FALSE.

   • Option (C): $\lim_{n \to \infty} \frac{f_1(n)}{f_2(n)} \neq \infty$, so $f_1(n) \notin \omega(f_2(n))$. Hence, (C) is FALSE.

   • Option (D): Since $f_1(n) < 2n$, we have $f_1(n) \in O(n)$. Hence, (D) is TRUE.