Consider functions Function_1 and Function_2 expressed in pseudocode as…

PYQ GATE 2023

Consider functions Function_1 and 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⌋\lfloor {n} / {2} \rfloor
            end while

    Function_2

            for i = 1 to 100 ∗ n do

                    x = x + 1;

            end for

Let f1(n)f_1(n) and f2(n)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.

    f1(n)∈Θ(f2(n))f_1(n) ∈ Θ(f_2(n))

  2. B.

    f1(n)∈o(f2(n))f_1(n) ∈ o(f_2(n))

  3. C.

    f1(n)∈ω(f2(n))f_1(n) ∈ ω(f_2(n))

  4. D.

    f1(n)∈O(n)f_1(n) ∈ O(n)

Attempted by 188 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…