Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
1
vote
1 answer

What is the result of $\frac{h^2}{2}O(h)+O(h^3)$

Why and how in the following expression $$ y_{n+1}=y_n+hy^{\prime}_n+\frac{1}{2}\left[ \frac{y^{\prime}_{n+1}-y^{\prime}_n}{h}+O(h) \right]h^2+O(h^3) $$ $$\Rightarrow y_{n+1}=y_n+h\left(…
Dante
  • 1,908
1
vote
1 answer

Do small o, small omega, and big theta cover all relationships between two functions

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true: $f(n) \in o(g(n))$ $f(n) \in \omega(g(n))$ $f(n) \in \Theta(g(n))$ Logically, this makes sense to me. For a homework assignment I'm given various functions…
Collin
  • 405
1
vote
1 answer

Asymptotic notation: Once $j$ is $\Theta(\log \log n)$

In the paper Wherefor Art Thou R3579X? they state at the end of page 5, while proving theorem 2.2, that "Once $j$ is $\Theta(\log \log n)$, each term in the sum is $O(1)$". My question is now what does "Once $j$ is $\Theta(\log \log n)$" mean? Does…
Omega
  • 43
1
vote
1 answer

Asymptotic behaviour of a sum

Let $p$ and $q$ be positive real numbers such that $p+q = 1$. am interested in in the large-$n$ behaviour of a following sum: \begin{equation} \sum\limits_{j=0}^{n-1} \left(1 + \frac{n-j-1/2}{j+1} \frac{q}{p}\right) C^{n-1}_j C^n_j…
Przemo
  • 11,331
1
vote
1 answer

Asymptotic Problem

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, using limit to find $\mathcal{O}(f(n))$, $\lim_{n\to\infty} \frac{2^{n+1}}{2^n}$we get 2 as answer 2 is less than infinity, so $f(n)$ belongs to $\mathcal{O}(g(n))$. But how is…
girl101
  • 333
1
vote
0 answers

How can I show that the solution of the recursive realtion is $O(n \lg n)$?

Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$. I am supposed to use the substitution method.. That's what I have tried: Let $T(n)=O(n \lg n)$ In order the recursive relation to be…
evinda
  • 7,823
1
vote
1 answer

Prove or disapprove the statement: $f(n)=O(g(n)) \Rightarrow 2^{f(n)}=O(2^{g(n)})$

Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disapprove the statement: $$f(n)=O(g(n)) \Rightarrow 2^{f(n)}=O(2^{g(n)})$$ That's what I have tried: $$f(n)=O(g(n)), \text{ so } \exists c>0 \text{ and } n_0 \geq 1 \text{ such…
evinda
  • 7,823
1
vote
1 answer

Big-Theta:What happens if $\displaystyle{a_d<0}$?

If $\displaystyle{f(n)=an^2+bn+c}$ with $\displaystyle{a>0}$ then $\displaystyle{f(n)=\Theta{(n^2)}}$. Generally, if $\displaystyle{f(n)=\sum_{i=0}^{d}a_in^i}$ with $\displaystyle{a_d>0}$ then $\displaystyle{f(n)=\Theta{(n^d)}}$. $$$$ But what…
Mary Star
  • 13,956
1
vote
2 answers

Asymptotic notation: A function is Θ-Notation

H. Cormen, Exercise 3.1-2 The following statement is true? If yes, prove that it is true. $$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$ I tried to expand $(n+a)^b$ using the Binomial theorem, but I couldn't solve this. Any help?
richardaum
  • 279
  • 1
  • 3
  • 12
1
vote
2 answers

$f(n) \in o(g(n))$ and $g(n) \in o(f(n))$

Could you help me with the following problem? Can there be two non-negative functions $f(n)$ and $g(n)$ such that $f(n) \in o(g(n))$ and $g(n) \in o(f(n))$? Just to make it clear, here is a definition of $o(g(n))$ (I am not talking about $O(g(n))$…
Smajl
  • 686
1
vote
1 answer

Need help in finding the asymptotic variance of an estimator.

I kinda doing some review questions for my finals and I kinda got stuck on this question. I'm able to do part a by finding the maximum likelihood estimator but for some reason. To find the variance I used $Var(\theta)=…
user131516
1
vote
0 answers

Simplify $\frac{n(k^2-1)}{2}$ to $ nk^2$

How does $\frac{n(k^2-1)}{2}$ become $nk^2$? I'm sorry for the stupid question but I'm at wits end and I have no idea how to go about this. Context Thanks
user149551
  • 11
1
vote
1 answer

What is $O\Big((n+1)!\Big)$?

What is $f(n) = (n+1)!$ which is also $f(n) = (n+1)n!$ in terms of big-O notation? My guess is $O(n \cdot n!)$ but I am not sure. I only know it is certainly $f(n) \in O(n^n)$.
Roman Volkov
  • 123
1
vote
0 answers

Asymptotic estimate for an expression of

\begin{equation} A = \frac{(\frac12-\frac{1}{n})(\frac12-\frac{2}{n})...(\frac12-\frac{t-1}{n})}{(\frac{1}{2}+\frac{1}{n})(\frac{1}{2}+\frac{2}{n})... (\frac{1}{2}+\frac{t}{n})} \end{equation} Can we get an asymptotic estimate for above A? Assume $n…
cinvro
  • 329
1
vote
1 answer

Prove the following $\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$

I want to prove the following by definition of asymptotic notation $$\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$$ Any suggestions?
user2976686
  • 185
  • 8
1 2 3
…
74 75