The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged asymptoticnotations
Notations
+33
votes
4
answers
1
GATE201534
Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$: $\Theta(n^4)$ $\Theta(n^5)$ $O(n^5)$ $\Omega(n^3)$ The equality above remains correct if $X$ is replaced by Only I Only II I or III or IV but not II II or III or IV but not I
asked
Feb 14, 2015
in
Algorithms
by
jothee
Veteran
(
105k
points)

3.7k
views
gate20153
algorithms
asymptoticnotations
normal
0
votes
1
answer
2
Let f(n) = O(n), g(n) = θ(n), and h(n) = Ω(n). Then f(n). h(n) + g(n) is_______________
asked
Jan 22, 2015
in
Algorithms
by
saurav04
Active
(
1.5k
points)

1.2k
views
algorithms
asymptoticnotations
+23
votes
5
answers
3
GATE2004IT55
Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$. Which one of the following statements is FALSE? $f(n) + g(n) = O(h(n) + h(n))$ $f(n) = O(h(n))$ $h(n) \neq O(f(n))$ $f(n)h(n) \neq O(g(n)h(n))$
asked
Nov 2, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

2.4k
views
gate2004it
algorithms
asymptoticnotations
normal
+35
votes
2
answers
4
GATE2008IT10
Arrange the following functions in increasing asymptotic order: $n^{1/3}$ $e^n$ $n^{7/4}$ $n \log^9n$ $1.0000001^n$ a, d, c, e, b d, a, c, e, b a, c, d, e, b a, c, d, b, e
asked
Oct 28, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

3.9k
views
gate2008it
algorithms
asymptoticnotations
normal
+21
votes
2
answers
5
GATE19961.11
Which of the following is false? $100n \log n=O(\frac{n\log n}{100})$ $\sqrt{\log n} = O(\log\log n)$ If $0 < x < y \text{ then } n^x = O\left(n^y\right)$ $2^n \neq O\left(nk\right)$
asked
Oct 9, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

3.9k
views
gate1996
algorithms
asymptoticnotations
normal
+20
votes
4
answers
6
GATE19941.23
Consider the following two functions: $g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n \geq 10,000 \end{cases}$ $g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}$ Which of the following is true? ... $g_1(n) \text{ is } O(n^3)$ $g_2(n) \text{ is } O(g_1(n))$ $g_2(n) \text{ is } O(n)$
asked
Oct 4, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

2.7k
views
gate1994
algorithms
asymptoticnotations
normal
+26
votes
3
answers
7
GATE201137
Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$? $f_1(n) = 2^n$ $f_2(n) = n^{3/2}$ $f_3(n) = n \log_2 n$ $f_4(n) = n^{\log_2 n}$ $f_3, f_2, f_4, f_1$ $f_3, f_2, f_1, f_4$ $f_2, f_3, f_1, f_4$ $f_2, f_3, f_4, f_1$
asked
Sep 29, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

2.2k
views
gate2011
algorithms
asymptoticnotations
normal
+30
votes
6
answers
8
GATE19992.21
If $T_1 = O(1)$, give the correct matching for the following pairs: $\begin{array}{ll}\hline \text{(M) $T_n = T_{n1} + n$} & \text{(U) $T_n = O(n)$} \\\hline \text{(N) $T_n = T_{n/2} + n$} & \text{(V) $T_n = O(n \log n)$} \\\hline \text{(O) $ ... $\text{MW, NU, OX, PV}$ $\text{MV, NW, OX, PU}$ $\text{MW, NU, OV, PX}$
asked
Sep 23, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

3.5k
views
gate1999
algorithms
recurrence
asymptoticnotations
normal
+24
votes
3
answers
9
GATE200537
Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$ Which one of the following is FALSE? $T(n)=O(n^2)$ $T(n)=\Theta(n \log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n \log n)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

2.4k
views
gate2005
algorithms
asymptoticnotations
recurrence
normal
+43
votes
4
answers
10
GATE200429
The tightest lower bound on the number of comparisons, in the worst case, for comparisonbased sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

8.3k
views
gate2004
algorithms
sorting
asymptoticnotations
easy
+35
votes
1
answer
11
GATE200320
Consider the following three claims: $(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants $2^{n+1} = O(2^n)$ $2^{2n+1} = O(2^n)$ Which of the following claims are correct? I and II I and III II and III I, II, and III
asked
Sep 16, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

3.4k
views
gate2003
algorithms
asymptoticnotations
normal
+36
votes
6
answers
12
GATE20011.16
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? $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$ $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$ $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$ $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

3.3k
views
gate2001
algorithms
asymptoticnotations
timecomplexity
normal
+44
votes
6
answers
13
GATE20002.17
Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true? $h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)$ is not $O(f(n))$ $f(n)$ is $O(g(n))$
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

6.7k
views
gate2000
algorithms
asymptoticnotations
normal
+20
votes
5
answers
14
GATE200839
Consider the following functions: $f(n) = 2^n$ $g(n) = n!$ $h(n) = n^{\log n}$ Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ ... $h\left(n\right)=O\left(f\left(n\right)\right); g\left(n\right) = \Omega\left(f\left(n\right)\right)$
asked
Sep 12, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

2.8k
views
gate2008
algorithms
asymptoticnotations
normal
+26
votes
4
answers
15
GATE201218
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$
asked
Aug 5, 2014
in
Algorithms
by
gatecse
Boss
(
16.8k
points)

3.4k
views
gate2012
algorithms
easy
asymptoticnotations
Page:
« prev
1
...
6
7
8
9
10
11
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
Amazing work Sir
50,645
questions
56,542
answers
195,692
comments
101,530
users