Dark Mode

Recent questions tagged asymptotic-notation

1 vote

1 answer

481

State the true and False (Beautiful Problem)
I was surfing internet and I got this beautiful Problem, I thought i should post here.

rude asked in Algorithms Jun 1, 2016

by rude

519 views

1 vote

2 answers

482

Analysis of code fragment to find time complexity [ACE Gate Practice Booklet Volume 1 Page 127 Question 32]

APOORV PANSE asked in Algorithms Jun 1, 2016

by APOORV PANSE

3.0k views

0 votes

1 answer

483

Asymptotics notations
It is true or false..(log n)! and (log log n)! are polynomially bounded? What does polynomially bounded means?

gshivam63 asked in Algorithms May 31, 2016

493 views

3 votes

1 answer

484

CMI2012-A-08
You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements: Algorithm $A$ will sort any array faster than algorithm $B$. On an average, algorithm $A$ will sort a given array faster ... be preferable to algorithm $B$. Which of the statements above are true? I, II and III I and III II and III None of them

go_editor asked in Algorithms May 22, 2016

1.4k views

6 votes

2 answers

485

T(n) = T(n-1) + T(n/2) + n
Consider the recurrence relation T(n) = T(n-1) + T(n/2) + n Which of the following is a good tight upper bound on T(n) (a) $\Theta (n^{2})$ (b) $\Theta (n^{2}\log n)$ (c) $\Theta (2^{(\log n)^{2}})$ (d) $\Theta (n^{(\log n)^{2}})$

$ourav asked in Algorithms May 20, 2016

by $ourav

13.8k views

0 votes

1 answer

486

can we say that 3n+2=O(-n)?
If f(n)=3n+2 then we can say that 3n+2<=(-4)(-n) .Can constant be negative in asymptotic notation?

debdas asked in Algorithms May 19, 2016

by debdas

1.6k views

0 votes

2 answers

487

Asymptotic comparison of functions
How will you perform asymptotic comparison of the following three functions: 1. $\log{n}$, 2. $(\log{n})^c$ and 3. $\sqrt{n}$ Obviously $\log{n} < (\log{n})^c$. But where $\sqrt{n}$ fits?

GateAspirant999 asked in Algorithms May 4, 2016

by GateAspirant999

1.5k views

0 votes

1 answer

488

what are the upper and lower bounds of n! ??

papesh asked in Algorithms May 3, 2016

by papesh

630 views

3 votes

2 answers

489

A better guess on upper bound
It's a question from Cormen book Exercise 4.4-5 and is described like this: Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(\frac{n}{2})+n$

SomnathKayal asked in Algorithms Apr 14, 2016

by SomnathKayal

885 views

0 votes

1 answer

490

Algorithms ,finding the upper bound n0 and constants
2n^2 +nlogn =theta(n^2) ,I have done the lower bound..Like finding out the n0 and the constant.. Help me with the upper bound constant and n0

Ritaban Basu_23 asked in Algorithms Mar 31, 2016

by Ritaban Basu_23

562 views

1 vote

1 answer

491

Ace Test Series: Algorithms - Asymptotic Notations
Consider the following functions: $f(n)=3n^{\sqrt(n) }$ $g(n) =2^{\sqrt(n)}\log_2 n$ $h(n)=n!$ Which of the following option is true? (A) $f(n)$ is $O(g(n))$ (B) $h(n)$ is $O(g(n))$ (C) $g(n)$ is not $O(f(n))$ (D) $h(n)=O(f(n))$

Registered user 7 asked in Algorithms Feb 3, 2016

by Registered user 7

717 views

1 vote

1 answer

492

MadeEasy Test Series: Algorithms - Asymptotic Notations
Let $f(n)$ = Ω(n) and g(n) = O(f(n)). Then g(n) = _______ [Assume n>0 ] (a.) Ω(n) (b.) O(n) (c.) θ(n) (d.) Ω(1) According to me, the answer should be (b.) since, f(n) has lowest bound n and g(n) has f(n) as upper bound. Answer given is (d.) I am confused about the answer.

Utk asked in Algorithms Feb 1, 2016

by Utk

629 views

0 votes

1 answer

493

f(n)=log n! ,g(n)=n logn what is the relationship between them?

nilamd asked in DS Jan 31, 2016

by nilamd

2.8k views

0 votes

3 answers

494

Given two positive functions f(n) and g(n).If f(n)/g(n)=c , for some constant c >=0 , which of the stmts are true ?

radha gogia asked in Algorithms Jan 29, 2016

2.1k views

1 vote

2 answers

495

Asymptotic bounds
how to solve the recurrence relation T(n)=16T(n/4)+n^2+nlogn

Murali asked in Programming in C Jan 22, 2016

by Murali

498 views

1 vote

3 answers

496

Let f(n) = Ω(n), and g(n) = O(f(n)). Then g(n) = _______ [Assume n > 0] 1. Ω(n) 2. O(n) 3. θ(n) 4. Ω(1)

Vaijenath Biradar asked in Algorithms Jan 19, 2016

by Vaijenath Biradar

1.6k views

0 votes

3 answers

497

Let f(x), g(x) and h(x) be function which of following statement is false?
Let $f(x),g(x)$ and $h(x)$ be functions which of the following statement is false? a). if $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$ then $f(x)$ is $O(h(x))$. b). if $f(x)$ ... $(b)$ I mean according to me , option (a) is correct , right ? by the rule of transitivity . Please correct me , if I am wrong.

worst_engineer asked in Algorithms Jan 17, 2016

by worst_engineer

809 views

0 votes

1 answer

498

time complexity

shivanisrivarshini asked in Algorithms Jan 7, 2016

by shivanisrivarshini

429 views

6 votes

2 answers

499

Asymptotics
Find the False statement. $O(2^n) = O(3^n)$ $O(\log n^2) = O(\log n)$ $f(n) = O \left ( (f(n))^2 \right )$ $2^{2 \log n} (\log n) = O(n^2 \log n)$

Himanshu1 asked in Algorithms Jan 6, 2016

826 views

4 votes

2 answers

500

Madeeasy
Which of the following is true? $f(n)=O\left(\left(f\left(n\right)\right)^{2}\right)$ $f(n)=O\left(g\left(n\right)\right)\Rightarrow 2^{f\left (n\right)}=O\left(2^{g\left(n\right)}\right)$ $f(n)+O\left(f\left(n\right)\right)=\theta \left(f\left(n\right)\right)$ Both (a) and (b)

saurav04 asked in Algorithms Jan 4, 2016

1.0k views

0 votes

3 answers

501

True/False
(logn)1/2=O(loglogn)

piyushkr asked in Algorithms Dec 31, 2015

1.4k views

1 vote

1 answer

502

Below question asked in GATE 1993. In this 1<=k<=n mentioned however k not using anywhere in notation.

piyushkr asked in Algorithms Dec 31, 2015

1.7k views

0 votes

1 answer

503

What is the simplification of the below mentioned expression -
n^(1/(2^(log2log2n)))

piyushkr asked in Algorithms Dec 31, 2015

318 views

0 votes

2 answers

504

How to evaluate below expression involving asymptotic notations?
If f(n)=ϴ(n),g(n)=ϴ(n) and h(n)=Ω(n) Then how to evaluate f(n)g(n)+h(n)? I am getting expression such that it is equivalent to O(n^2 ) , since f(n)g(n)=theta(n^2),Now I am just confused at one point that how to proceed for calculating f(n)g(n)+h(n) ,theta(n^2)+h(n) ?

radha gogia asked in Algorithms Dec 31, 2015

361 views

0 votes

1 answer

505

what is the relation between two functions ?
A) nlg c , clg n , B) lg(n!) , lg(nn) I guess both are equivalent so then how to represent them using asymptotic notation ?

radha gogia asked in Algorithms Dec 29, 2015

438 views

1 vote

1 answer

506

Asymptotics
Ans given is D. Is it because, in analyzing this we would ignore the constants involved in the equation?

UK asked in Algorithms Dec 29, 2015

by UK

418 views

0 votes

1 answer

507

How do O and Ω relate to worst and best case?
I am unable to get the actual significance of the asymptotic notations with respect to best , worst and average case , for instance why is worst case of insertion sort theta(n^2) , why not O(n^2) more specifically . Also why ... please clarify this precisely . http://cs.stackexchange.com/questions/23068/how-do-o-and-%CE%A9-relate-to-worst-and-best-case

radha gogia asked in Algorithms Dec 26, 2015

658 views

50 votes

6 answers

508

TIFR CSE 2016 | Part B | Question: 7
Let $n = m!$. Which of the following is TRUE? $m = \Theta (\log n / \log \log n)$ $m = \Omega (\log n / \log \log n)$ but not $m = O(\log n / \log \log n)$ $m = \Theta (\log^2 n)$ $m = \Omega (\log^2 n)$ but not $m = Ο(\log^2 n)$ $m = \Theta (\log^{1.5} n)$

Rohith AP asked in Algorithms Dec 13, 2015

6.1k views

2 votes

1 answer

509

asymptotic notation
show that k lnk =ϴ(n) then k=ϴ(n/lg n)

Pooja Palod asked in Algorithms Dec 5, 2015

299 views

1 vote

2 answers

510

true / false
i geeting ans 1 and 2 are true but ans given only 2 is true explain it

Banti Arya asked in Algorithms Dec 5, 2015

513 views

Page:

« prev
1
...
12
13
14
15
16
17
18
19
next »

Recent questions tagged asymptotic-notation