Home › Previous year questions › GATE 2021 CS (CS1) › Question 13GATE 2021 CS (CS1) – Question 13 Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice
Consider the following three functions. $f_1 = 10^n$, $f_2 = n^{\log n}$, $f_3 = n^{\sqrt{n}}$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
$f_3, f_2, f_1$ $f_2, f_1, f_3$ $f_1, f_2, f_3$ $f_2, f_3, f_1$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (D) $f_2, f_3, f_1$
Explanation Taking logs: $\log f_2 = \log^2 n$, $\log f_3 = \sqrt{n}\log n$, $\log f_1 = n\log 10$. Growth order is $f_2 < f_3 < f_1$.
More Asymptotic Analysis and Time/Space Complexity questions GATE 2021 CS (CS1) Q40 – Consider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n if n>0; T(n)=1 if… GATE 2020 CS Q12 – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is GATE 2019 CS Q47 – There are n unsorted arrays: A 1,A 2,,A n. Assume that n is odd. Each of A 1,A 2,,A n… GATE 2015 CS (CS1) Q60 – An algorithm performs ( N)1/2 find operations, N insert operations, ( N)1/2 delete… GATE 2015 CS (CS1) Q64 – Consider the following C function. Which one of the following most closely approximates… GATE 2017 CS (CS1) Q14 – Consider the following functions from positive integers to real numbers: 10, n, n, 2 n,… All Asymptotic Analysis and Time/Space Complexity questions →