GATE CS 2023 (Forenoon) — Question 54

AlgorithmsAsymptotic Analysis (O, Omega, Theta Complexities)MSQ2 marksMedium

Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Function 1
code
1while n > 1 do
2    for i = 1 to n do
3        x = x + 1;
4    end for
5    n = \lfloor n/2 \rfloor;
6end while
7
Function 2
code
1for i = 1 to 100 * n do
2    x = x + 1;
3end for
4
Let \(f_1(n)\) and \(f_2(n)\) denote the number of times the statement "x = x + 1" is executed in Function_1 and Function_2, respectively. Which of the following statements is/are TRUE?
  1. A
    \(f_1(n) \in \Theta(f_2(n))\)
  2. B
    \(f_1(n) \in o(f_2(n))\)
  3. C
    \(f_1(n) \in \omega(f_2(n))\)
  4. D
    \(f_1(n) \in O(n)\)
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Asymptotic Analysis (O, Omega, Theta Complexities)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group