GATE CSE 2023 | Question: 44

Question

Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ expressed in pseudocode as follows:

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 = ⌊n/2⌋;            |    
end while                     |    

Let $f_{1}(n)$ and $f_{2}(n)$ denote the number of times the statement $\textsf{“x = x + 1”}$ is executed in $\textsf{Function_1}$ and $\textsf{Function_2},$ respectively.

Which of the following statements is/are $\text{TRUE}?$

• A. $f_{1}(n) \in \Theta\left(f_{2}(n)\right)$
• B. $f_{1}(n) \in o\left(f_{2}(n)\right)$
• C. $f_{1}(n) \in \omega\left(f_{2}(n)\right)$
• D. $f_{1}(n) \in O(n)$

Comments

$\text{Function_1}$ iterates for $n$ times.

$\therefore f_1(n)=n$

$\text{Function_2}$ iterates for $100*n$ times. (Asymptotically $n$ times)

$\therefore f_2(n) = n $

So we can conclude,

$f_1(n) \in \Theta(f_2(n))$

$f_1(n) \in O(f_2(n))$

$f_1(n) \in \Omega(f_2(n))$

$Ans-A,D$

Answer 1

 

.

Answer 2

Lets analyze Function_1

1. It has a for loop inside the while which runs for $n$ times
2. The $n$ is halved every iteration of the while loop

We would sum up the the number of times the inner loop (as its the only block which isn’t const time)

$S(n) = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} \cdots + 1$

(We can assume n was a power of 2 WLOG)

To get the number of terms $p$
$1 = n (\frac{1}{2})^{p}$

$p = log_2(n)$
$\frac{1}{n} = (\frac{1}{2})^p$

 

Now if we sum it up.

$S(n) = n \cdot \frac{1-\frac{1}{2}^p}{1-\frac{1}{2}}$
$S(n) = 2n-2$
 

 

Now for function_2

Its a simple for loop which runs for $100n$

Both of the functions belong to $\theta(n)$

Hence A and D are correct

D because we also consider equality in big-O

Comments

Since S(n) is decreasing GP, we can directly say the TC will be big O of “n” only, as we consider the first term of gp only [in decreasing gp].

If it was increasing gp, we’ll have TC to be  big oh of last term.

 

Can u explain how you find number of terms with your approach?

Answer 3

(A.)  f1(n) ∈ Θ (f2(n) ∴ f1(n) = f2(n)

(D.)  f1(n) ∈ O (f2(n) ∴ f1(n) <= O(n)

Answer 4

Function_1 :- The for loop in function_1 will run 'n' times, but the outer while loop will change the value of 'n' to half each time.
Therefore, f₁(n) = n + (n/2) + (n/4) + (n/8) + ...  = n/(1-0.5) = 2n

Function_2 :- The for loop in function_2 will run '100n' times. Therefore, f₂(n) = 100n

Theta(f₂(n)) represents the set of all those functions who is asymptotically equal to f₂(n). 
Similarly, small-oh(f₂(n)) represents the set of all those functions who is asymptotically smaller than f₂(n). And small-omega(f₂(n)) represents the set of all those functions who is asymptotically greater than f₂(n).

example :- small-oh(n) represents the set of all those functions who is asymptotically smaller than equal to n. 
small-oh(n) = {n, 2n, 3n, log(n), 100, ...} (all these functions are asymptotically smaller than equal to n)

Ans is A,D.