For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).

GATE 2015 CS (CS3) – Question 64

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

For positive integer n, $f(n)=n$ and $g(n)=n^{1+\sin n}$. Which hold? I: f=O(g). II: f=Ω(g).

I only
II only
Both
Neither

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Neither

Explanation

The ratio is $f/g=n^{-\sin n}$. Integer arguments modulo 2π visit intervals where sin n is bounded above zero and intervals where it is bounded below zero infinitely often. Along the first subsequence the ratio tends to zero, and along the second it grows without bound. Thus neither an eventual positive lower bound nor a finite upper bound exists. Answer D.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2021 CS (CS2) Q49 – For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual…
GATE 2026 CS (CS1) Q17 – Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T…
GATE 2026 CS (CS1) Q47 – Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that…
GATE 2026 CS (CS2) Q24 – Consider the following functions, where n is a positive integer: n1/3, n, (n!), and 2 n.…
GATE 2026 CS (CS2) Q25 – Which of the following can be recurrence relation(s) corresponding to an algorithm with…
GATE 2026 CS (CS2) Q38 – Consider an array A of integers of size n with indices from 1 to n. An algorithm is to be…

All Asymptotic Analysis and Time/Space Complexity questions →