GATE CSE 2023 | Question: 44

Question

Consider functions $\textsf{Function_1}$ and $\textsf{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 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 $\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

f1​(n) is not strictly smaller than f2(n)---------> B is false
 

the ratio is a finite constant, not infinity.

 f1​(n) does not dominate  f2​(n)------->C is false

---

• Θ → same growth rate (constant ratio)

• o → strictly smaller (ratio → 0)

• ω → strictly larger (ratio → ∞)

 

---

Recap.  For big 0  <=

For small 0.   <

For theta.  =

For big omega >=

For small omega >

---

oh god ! i saw the qn and thought function1 to run logn times ! by seeing n/2

 

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?

---

nice explaination

---

Love thos approahh more than the standard answer. No room for ambiuity cuz calculated te exact sum.

---

Nice explanation, but I think there is a small mistake in calculating total number of statement(x=x+1) executions by Function 1  (though it’s definitely not a big concern to for this question)

Answer 3

 

 

Comments

int fun(int n) {
    int i, j;
    for(i=1; i<=n; i++) {
        for (j=1; j<n; j+=i) {
            printf("%d %d", i, j);
        }
    }
}
this is also a previous year question
time complexity of fun is calculated same as f1 here T.C of fun is nlogn when should we take nlogn and when n

---

@KrishnaVardhan, Can you paste the link of that previous question ?

---

@Shaik Masthan
check Here..

---

@KrishnaVardhan, 

In this question loop will like:

$n.(\frac{1}{1}+\frac{1}{2}+\frac{1}{2^2}+....+\frac{1}{2^{k-1}}+\frac{1}{2^k}) \Rightarrow multiple\; of\; \frac{1}{2} $

 

In Gate2017 question it is like:

$n.(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+....+\frac{1}{{n-1}}+\frac{1}{n}) \Rightarrow not multiple\; of\; \frac{1}{2} $

Answer 4

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

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

Answer 5

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.

Comments

Small-oh means f1 is strictly smaller than n

Answer 6

A AND D ANSWER