Question:
Which one of the following statements is TRUE for all positive functions \( f(n) \)?
Which one of the following statements is TRUE for all positive functions \( f(n) \)?
Show Hint
For polynomial functions, \( f(n^2) \) and \( f(n)^2 \) grow at the same rate. The notation \( \Theta \) is used for functions that grow at the same rate asymptotically.
Updated On: Jan 30, 2026
- \( f(n^2) = \Theta(f(n)^2) \), when \( f(n) \) is a polynomial
- \( f(n^2) = o(f(n)^2) \), when \( f(n) \) is an exponential function
- \( f(n^2) = O(f(n)^2) \), when \( f(n) \) is an exponential function
- \( f(n^2) = \Omega(f(n)^2) \)
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
For polynomial functions, \( f(n^2) \) and \( f(n)^2 \) have the same growth rate. This is because both grow at a polynomial rate, and squaring \( f(n) \) is equivalent to applying the function to \( n^2 \). Hence, statement (A) is correct, and the other statements do not hold universally for all positive functions.
Final Answer: (A)
Final Answer: (A)
Was this answer helpful?
0
0
Top GATE CS Algorithms Questions
- Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \( G \) is/are TRUE?
- Let \( G \) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \( \alpha \) is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \( G \) before and after the edge weight update?
- Consider the following recurrence relations. For all \(n > 1\),
\[ T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n) \]
\[ T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n) \]
Assume that for all \(n \leq 1\), \(T_1(n) = 1\) and \(T_2(n) = 1\).
Which one of the following options is correct? - Let \(G(V,E)\) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let \(s \in V\) be a vertex in \(G\). For every \(u \in V\) and for every \(k \geq 0\), let \(d_k(u)\) denote the weight of a shortest path (in terms of weight) from \(s\) to \(u\) of length at most \(k\). If there is no path from \(s\) to \(u\) of length at most \(k\), then \(d_k(u) = \infty\).
Consider the statements:
S1: For every \(k \geq 0\) and \(u \in V\), \(d_{k+1}(u) \leq d_k(u)\).
S2: For every \((u,v) \in E\), if \((u,v)\) is part of a shortest path (in terms of weight) from \(s\) to \(v\), then for every \(k \geq 0\), \(d_k(u) \leq d_k(v)\).
Which one of the following options is correct? - Let \(G(V, E)\) be a simple, undirected graph. A vertex cover of \(G\) is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in \(G\) be \(k\). Let \(S\) be any vertex cover of size \(k\).
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\)?
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions