menu
search
Log In
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

Subjects

Recent questions tagged asymptotic-notations

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged asymptotic-notations

0 votes
1 answer
1
NIELIT 2016 MAR Scientist C - Section C: 18
Two alternative package $A$ and $B$ are available for processing a database having $10^{k}$ records. Package $A$ requires $0.0001 n^{2}$ time units and package $B$ requires $10n\log _{10}n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$
Two alternative package $A$ and $B$ are available for processing a database having $10^{k}$ records. Package $A$ requires $0.0001 n^{2}$ time units and package $B$ requires $10n\log _{10}n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$
asked Apr 2, 2020 in Algorithms Lakshman Patel RJIT 191 views
0 votes
2 answers
2
NIELIT 2017 July Scientist B (IT) - Section B: 59
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 445 views
0 votes
2 answers
3
UGCNET-Jan2017-III: 31
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n} $ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n} $ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
asked Mar 24, 2020 in Algorithms jothee 317 views
5 votes
4 answers
4
TIFR2020-B-10
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11, 2020 in Algorithms Lakshman Patel RJIT 613 views
0 votes
3 answers
5
By own
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
asked Sep 22, 2019 in Algorithms shubhamkks1005 146 views
0 votes
2 answers
6
From asymptotic notation
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
asked Sep 22, 2019 in Algorithms shubhamkks1005 144 views
0 votes
1 answer
7
Cormen Edition 3 Exercise 8.1 Question 2 (Page No. 194)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 85 views
0 votes
1 answer
9
Cormen Edition 3 Exercise 2.2 Question 4 (Page No. 29)
How can we modify almost any algorithm to have a good best-case running time?
How can we modify almost any algorithm to have a good best-case running time?
asked Jun 25, 2019 in Algorithms akash.dinkar12 80 views
0 votes
1 answer
10
Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked Jun 12, 2019 in Algorithms lolster 331 views
3 votes
1 answer
11
asymptotic_Notations Self_Doubt
Please give an example case for which all the three conditions $f(n)\neq O(g(n))$, $f(n)\neq \Theta (g(n))$ and $f(n)\neq \Omega (g(n))$ holds true.
Please give an example case for which all the three conditions $f(n)\neq O(g(n))$, $f(n)\neq \Theta (g(n))$ and $f(n)\neq \Omega (g(n))$ holds true.
asked Jun 1, 2019 in Algorithms Satbir 407 views
1 vote
2 answers
13
Asymptotic Notation theta property
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked May 26, 2019 in Algorithms shubhojit1412 633 views
0 votes
0 answers
16
Cormen Edition 3 Exercise 3.2 Question 8 (Page No. 60)
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 47 views
0 votes
0 answers
17
Cormen Edition 3 Exercise 3.2 Question 7 (Page No. 60)
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.
asked Apr 4, 2019 in Algorithms akash.dinkar12 40 views
0 votes
0 answers
18
Cormen Edition 3 Exercise 3.2 Question 6 (Page No. 60)
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 35 views
1 vote
0 answers
20
Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
21
Cormen Edition 3 Exercise 3.2 Question 1 (Page No. 60)
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
22
Cormen Edition 3 Exercise 3.1 Question 8 (Page No. 53)
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ ... all $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ there exist positive constants $c,n_0,$ and ... $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 65 views
0 votes
0 answers
24
Cormen Edition 3 Exercise 3.1 Question 6 (Page No. 53)
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
26
Cormen Edition 3 Exercise 3.1 Question 3 (Page No. 53)
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.
asked Apr 4, 2019 in Algorithms akash.dinkar12 55 views
0 votes
1 answer
27
Cormen Edition 3 Exercise 3.1 Question 2 (Page No. 52)
Show that for any real constants $a$ and $b$, where $b > 0,$ $(n+a)^b=\Theta(n^b)$
Show that for any real constants $a$ and $b$, where $b > 0,$ $(n+a)^b=\Theta(n^b)$
asked Apr 4, 2019 in Algorithms akash.dinkar12 71 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...