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
0
votes
3
answers
1
Asymptotic Notation
Describe a Θ(nlgn)time algorithm that, given a set S of n integers and another integer x, determines whether or not there exists two elements of S whose sum is exactly x.
asked
May 27, 2015
in
Algorithms
by
spriti1991
Active
(
1.9k
points)

452
views
asymptoticnotations
algorithms
+43
votes
6
answers
2
GATE2015342
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? $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ Only I Only II Both I and II Neither I nor II
asked
Feb 15, 2015
in
Algorithms
by
jothee
Veteran
(
106k
points)

4.9k
views
gate20153
algorithms
asymptoticnotations
normal
+34
votes
4
answers
3
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
(
106k
points)

4.2k
views
gate20153
algorithms
asymptoticnotations
normal
0
votes
1
answer
4
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.6k
points)

1.3k
views
algorithms
asymptoticnotations
+23
votes
5
answers
5
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.6k
views
gate2004it
algorithms
asymptoticnotations
normal
+38
votes
2
answers
6
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)

4.3k
views
gate2008it
algorithms
asymptoticnotations
normal
+22
votes
2
answers
7
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.3k
points)

4.3k
views
gate1996
algorithms
asymptoticnotations
normal
+24
votes
4
answers
8
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.3k
points)

2.9k
views
gate1994
algorithms
asymptoticnotations
normal
+27
votes
3
answers
9
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
(
106k
points)

2.5k
views
gate2011
algorithms
asymptoticnotations
normal
+32
votes
6
answers
10
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.3k
points)

3.9k
views
gate1999
algorithms
recurrence
asymptoticnotations
normal
+24
votes
3
answers
11
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.3k
points)

2.7k
views
gate2005
algorithms
asymptoticnotations
recurrence
normal
+46
votes
4
answers
12
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.3k
points)

9.1k
views
gate2004
algorithms
sorting
asymptoticnotations
easy
+35
votes
1
answer
13
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.3k
points)

3.7k
views
gate2003
algorithms
asymptoticnotations
normal
+40
votes
6
answers
14
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.3k
points)

3.6k
views
gate2001
algorithms
asymptoticnotations
timecomplexity
normal
+46
votes
7
answers
15
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.3k
points)

7.3k
views
gate2000
algorithms
asymptoticnotations
normal
+23
votes
5
answers
16
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.3k
points)

3.1k
views
gate2008
algorithms
asymptoticnotations
normal
+27
votes
4
answers
17
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
(
17.6k
points)

3.8k
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
My Experience at IIT Madras and Some Insights
GATE Meetup at CSA IISC on February 29 as part of CSA Open Day
Make Rank Predictor Dynamic (Again?)
ISI exam 2020
Knowing All features of Pragy's App
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
please login and checked syllabus
Start attempting the basic challenges on...
For Computer Scienece/IT Paper 2,Engineering...
As per my knowledge syllabus is same as that of...
Hello guys, can someone guide us on how to...
50,832
questions
57,685
answers
199,268
comments
107,174
users