Growth rate comparisons look like free marks until two functions refuse to separate by inspection. Is n^(log n) bigger than 2^n? Does n^2 log n beat n(log n)^10? The reliable method is to compare logarithms and remember that every genuine fixed-base exponential eventually beats every polynomial. Eleven GATE questions and one UGC NET question below push that method through the five shapes examiners keep returning to: order a list of functions, pick the winner of a two-function duel, judge a set of O and Theta claims, probe the definitions at their edge cases, and invert a running time into a problem size.
1. The growth ladder and the log trick, in 60 seconds
Keep this eventual growth ladder in mind:
constant < log n < sqrt(n) < n < n log n < n^(3/2) < n^(7/4) < n^(log n) < fixed-base exponentials < n!
Within the exponential family, the larger base grows faster. The function n^(log n) lies between polynomials and true exponentials because its logarithm is (log n)^2, which exceeds every fixed k log n but remains below every linear cn.
The log trick is simple: for positive f and g, compare log f and log g. At n = 1024, log2 n = 10. Therefore log2(n^(log2 n)) = (log2 n)^2 = 10^2 = 100, while log2(2^n) = n = 1024. Since 1024 > 100, 2^n is already astronomically larger on the original scale.
Two warnings matter. A lower-order function can be larger for small n because constants can hide the eventual trend. Also, O gives an upper bound, not an exact order, so several O-style statements can be true together.
2. Warm-up: ordering polynomials, logs and constants (Q1-Q2)
Q1. (GATE 2017, see the solved page) Consider the following functions from positive integers to real numbers: 10, sqrt(n), n, log2 n, 100/n. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
(a) log2 n, 100/n, 10, sqrt(n), n
(b) 100/n, 10, log2 n, sqrt(n), n
(c) 10, 100/n, sqrt(n), log2 n, n
(d) 100/n, log2 n, 10, sqrt(n), n
Answer: (b). The term 100/n decreases towards zero, while 10 stays constant and log2 n eventually exceeds every constant. Then log2 n < sqrt(n) < n, so evaluating only at n = 1 creates the trap.
Q2. (GATE 2011, see the solved page) Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4? f1(n) = 2^n, f2(n) = n^(3/2), f3(n) = n log n, f4(n) = n^(log n)
(a) f3, f2, f4, f1
(b) f3, f2, f1, f4
(c) f2, f3, f1, f4
(d) f2, f3, f4, f1
Answer: (a). Since log n < sqrt(n), n log n < n^(3/2). For the top pair, log f4 = (log n)^2 and log f1 is proportional to n; n dominates (log n)^2, giving f3 < f2 < f4 < f1.
3. The classic orderings GATE keeps recycling (Q3-Q4)
Q3. (GATE 2008, see the PYQ page for this topic) Arrange the following functions in increasing asymptotic order: A. n^(1/3), B. e^n, C. n^(7/4), D. n log^9 n, E. 1.0000001^n
(a) A, D, C, E, B
(b) D, A, C, E, B
(c) A, C, D, E, B
(d) A, C, D, B, E
Answer: (a). A is the smallest polynomial term. For D versus C, cancel n: log^9 n < n^(3/4), so D < C. Even the tiny base 1.0000001 makes E a genuine exponential that beats every polynomial, while e > 1.0000001 gives E < B.
Q4. (GATE 2021, see the solved page) Consider the following three functions. f1 = 10^n, f2 = n^(log n), f3 = n^(sqrt n). Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
(a) f3, f2, f1
(b) f2, f1, f3
(c) f1, f2, f3
(d) f2, f3, f1
Answer: (d). Their logs have orders n, (log n)^2 and sqrt(n) log n, respectively. Since (log n)^2 < sqrt(n) log n < n, the original functions satisfy f2 < f3 < f1.
4. Head-to-head duels: which function wins? (Q5-Q6)
Q5. (GATE 2001, see the solved page) Let f(n) = n^2 log n and g(n) = n (log n)^10 be two positive functions of n. Which of the following statements is correct?
(a) f(n) = O(g(n)) and g(n) is not O(f(n))
(b) f(n) is not O(g(n)) and g(n) = O(f(n))
(c) f(n) = O(g(n)) and g(n) = O(f(n))
(d) f(n) is not O(g(n)) and g(n) is not O(f(n))
Answer: (b). The ratio f(n)/g(n) = n log n/(log n)^10 = n/(log n)^9 tends to infinity. Thus f strictly dominates g because one extra factor of n beats any fixed power of log n.
Q6. (GATE 2008, see the solved page) Consider the following functions: f(n) = 2^n, g(n) = n!, h(n) = n^(log n). Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
(a) f(n) = O(g(n)); g(n) = O(h(n))
(b) f(n) = Omega(g(n)); g(n) = O(h(n))
(c) g(n) = O(f(n)); h(n) = O(f(n))
(d) h(n) = O(f(n)); g(n) = Omega(f(n))
Answer: (d). In log terms h is (log n)^2, f is n and g is n log n, since log(n!) = Theta(n log n), so h < f < g. Option (a) has one true clause, but g = O(h) is false, so always test every clause.
5. Claims, identities and the Theta algebra (Q7-Q9)
Q7. (GATE 2003, see the solved page) Consider the following three claims: 1. (n + k)^m = Theta(n^m), where k and m are constants, 2. 2^(n+1) = O(2^n), 3. 2^(2n+1) = O(2^n). Which of these claims are correct?
(a) 1 and 2
(b) 1 and 3
(c) 2 and 3
(d) 1, 2, and 3
Answer: (a). Claim 1 has leading order n^m, and claim 2 is 2^(n+1) = 2 x 2^n, only a constant multiple. Claim 3 becomes 2 x 4^n, and its ratio to 2^n is 2 x 2^n, which is unbounded.
Q8. (GATE 2015, see the solved page) Consider the equality sum over i = 0 to n of i^3 = X and the following choices for X: I. Theta(n^4), II. Theta(n^5), III. O(n^5), IV. Omega(n^3). The equality above remains correct if X is replaced by
(a) Only I
(b) Only II
(c) I or III or IV but not II
(d) II or III or IV but not I
Answer: (c). The closed form is [n(n+1)/2]^2 = n^2(n+1)^2/4 = Theta(n^4). It is also O(n^5) and Omega(n^3), but it cannot be Theta(n^5); O is an upper bound, not an equality claim.
Q9. (GATE 2022, see the PYQ page for this topic) Which one of the following statements is TRUE for all positive functions f(n)?
(a) f(n^2) = Theta(f(n)^2), when f(n) is a polynomial
(b) f(n^2) = O(f(n)^2)
(c) f(n^2) = O(f(n)^2), when f(n) is an exponential function
(d) f(n^2) = Omega(f(n)^2)
Answer: (a). For f(n) = n^k, f(n^2) = n^(2k) = (n^k)^2; lower-order polynomial terms do not change the Theta class. For f(n) = 2^n, however, f(n^2) = 2^(n^2) while f(n)^2 = 2^(2n), defeating (b) and (c); f(n) = log n defeats the universal lower bound in (d).
6. Definition-level teasers: O, o, Omega on edge cases (Q10-Q11)
Q10. (GATE 2023, see the solved page) Let f and g be functions of natural numbers given by f(n) = n and g(n) = n^2. Which of the following statements is/are TRUE? (MSQ, multiple answers)
(a) f in O(g)
(b) f in Omega(g)
(c) f in o(g)
(d) f in Theta(g)
Answer: (a) and (c). Since f/g = n/n^2 = 1/n tends to zero, f is strictly slower, so both little-o and big-O hold. An MSQ has no single correct choice, so both (a) and (c) have to be marked; the marking scheme for your cycle is in the official GATE information brochure.
Q11. (GATE 2015, see the PYQ page for this topic) Let f(n) = n and g(n) = n^(1 + sin n), where n is a positive integer. Which of the following statements is/are correct? I. f(n) = O(g(n)), II. f(n) = Omega(g(n))
(a) Only I
(b) Only II
(c) Both I and II
(d) Neither I nor II
Answer: (d). The ratio g/f = n^(sin n) has subsequences that grow without bound and others that tend to zero because sin n repeatedly takes positive and negative values bounded away from zero. Therefore neither function is an eventual ceiling for the other, so neither O nor Omega holds.
7. Growth rates as real time budgets (Q12)
Q12. (UGC NET 2020, see the solved page) If algorithm A and another algorithm B take log2(n) and sqrt(n) microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve, respectively, in one second are ______ and ______.
(a) 2^(10^n) and 10^6
(b) 2^(10^6) and 10^12
(c) 2^(10^6) and 6.10^6
(d) 2^(10^6) and 6.10^12
Answer: (b). One second = 10^6 microseconds. For A, log2 n = 10^6, so n = 2^(10^6); for B, sqrt(n) = 10^6, so n = (10^6)^2 = 10^12. Inverting the running time turns the ladder into a concrete budget: log time reaches 2^(10^6), while square-root time reaches 10^12.
8. Score yourself and what to drill next
If you scored 10 to 12, growth rates are settled, so move to recurrences and sorting analysis. At 7 to 9, repeat the log trick through Q2, Q4 and Q6. Below 7, revisit the asymptotic definitions before more PYQs, starting with Q10 and Q11.
For more solved sets, use the Algorithms MCQs blog, then try the adjacent Data Structures MCQs. The GATE CS subject weightage guide helps you place Algorithms inside the wider paper; confirm any specific mark distribution against recent official brochures.
Use the GATE Test Series, Mocks & Topic-wise Tests when you want timed algorithm tests and full mocks that mix these patterns. Choose Zero to Hero, Complete CS Course when you want to learn algorithm analysis through lectures instead of reverse-engineering it from answers. Then come back to these 12 with the options covered and rebuild each ordering from the log trick alone; when it falls out inside a minute, growth rates are behind you.
