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
2
votes
2 answers

How to find the asymptotic behavior of this function

I have a function that I want to study it's asymptotic behavior. The function is $$ f(k) = - \frac{k^2}{4} - \frac{\log\pi}{2} + \log\left( \frac12 \left| \mathrm{Erfi}(\frac{k}{2} - \pi i) - \mathrm{Erfi}(\frac{k}{2} + \pi i)\right|\right) $$ and…
xslittlegrass
  • 471
2
votes
3 answers

Big-O notation and polynomials

In my text, I am given that the sum of the first n positive integers can be understood in terms of big-O notation. ''Since each of the integers in the sum of the first $n$ positive integers does not exceed $n$'', we can write: $$1 + 2 + \cdots + n…
compguy24
  • 421
2
votes
2 answers

Prove ∀a∈R, ∀b∈R ,[(a <= b)⇒(n^a ∈O(n^b))]

We have just started learning the Big O notation and have been asked to prove this statement: $$ \forall a,b \in \mathbb{R}, a \leq b \implies n^a \in O(n^b) $$ I am really confused how to approach this problem, what are some of the steps we can…
user3343972
  • 121
2
votes
3 answers

big and small O notation help

I was hoping someone could help me answer this question. I can't wrap my head around this concept: Why is $\cal{O}(x^3) = o(x^2)$?
icobes
  • 1,109
2
votes
2 answers

Big O with cosine?

Consider the functions $f(n) = n\cdot \max(0,\cos(\pi n))$, $g(n) = n$. What is the relation between these functions in big-$\mathcal O$ notation? Assume $n$ takes on only positive integer values. For the cosine, the angle is being expressed in…
Public Display Name
  • 233
2
votes
1 answer

How do I prove that a constant $C$ exists that matches these bounds?

For $n \in \mathbb{Z}^+$, given any function $T(n)$ such that $T(n) = \Omega(n^3)$ and $T(n) = O(n^4)$, how can I prove that constants $C$ and $N$ exist such that $$ n^3 + 10 \le CT(n) \le n^4 $$ for all $n > N$? My initial attempts have stemmed…
David Faux
  • 3,425
2
votes
2 answers

Big O proof of statement

I am having a hard time proving that $n^k$ is $O(2^n)$ for all $k$. I tried taking $\log_2$ of both sides and have $k\cdot \log_2 n =n$ but this is wrong. I am not sure how else I can prove this. Thanks.
user629034
  • 319
2
votes
1 answer

Finding the Big-O of $n^{\sin^2n} \cdot \sqrt{n}$

I need to find the Big-O of $f(n) = n^{\sin^2n} \cdot \sqrt{n}$. I know that the value of $\sin(n)$ oscillates between -1 and 1, and so does the value of $\sin^2(n) = \sin ( \sin(n))$. Now, if I am required to be as accurate as possible, should I…
Pele
  • 23
2
votes
3 answers

Is it true that every function f satisfies $f(2n) = Θ(f(n))$?

I am trying to determine if this statement is correct or not: Every function f satisfies f(2n) = Θ(f(n)) Where, as I understand it, $f(2n)$ cannot be bounded by $f(n)$, as: f(n) ≤ f(2n) Since $2n$ is twice that of $n$, making me think that simply…
user2494584
  • 283
2
votes
1 answer

Asymptotic notation for logarithmic function

Can anyone explain to me how $$ f(n) = n^{0.999999} \log n = O(n^{0.999999} n^{0.000001}) $$ ?
bcp
  • 73
2
votes
2 answers

Properties of Big $\mathcal{O}$

I have seen in a paper that, if $A=\mathcal{O}(p^2)$ and $B=\mathcal{O}(p)$ then, how can we say that, $A^{-1/2}B$ is diverging? The way I thought is, if $A = \mathcal{O}(p^2)$, then $A^{-1/2}$ = $\mathcal{O}(p^{-1})$, then $A^{-1/2}B$ =…
shani
  • 779
  • 1
  • 5
  • 12
2
votes
1 answer

How do you simplify this big O sum?

I saw someone interpret $\sum_{i=1}^{n}\mathcal{O}\left(i^{k-2}\right)$ as $\mathcal{O}\left(n^{k-1}\right)$. Is this right? If so, can you explain?
Black Milk
  • 177
  • 7
2
votes
1 answer

Why does $af(n/b) \le cf(n)$ for $c < 1$ imply that $f(n) = \Omega(n^{\log_ba+\epsilon})$?

The Master method for solving recurrences of the kind $T(n) = aT(n/b) + f(n)$ has a third case, which requires a regularity condition to hold: $$ af(n/b) \le cf(n) \qquad a \ge 1, b > 1, c < 1$$ This should imply that $$ f(n) =…
Stefan Kanev
  • 397
2
votes
1 answer

Asymptotic expansion of $(1+\frac{t}{n})^{-n-1}$ at $n \to \infty$

I'm reading through a proof in Analytic Combinatorics by Flajolet/Sedgewick and I have come across this: We have the asymptotic…
MathStudent
  • 1,352
  • 11
  • 22
2
votes
1 answer

Proving that $3n^2 + n \log_2n - 2$ is $\Theta (n^2 - 5n +1)$

Specifically the following: $3n^2 + n \log_2n - 2 \in \Theta (n^2 - 5n +1)$ I'm aware it needs to be $g(n)c_1 \le f(n) \le g(n)c_2$, where $g(n)$ is $\Theta (n^2 - 5n +1)$ and $f(n)$ is $3n^2 + n \log_2n - 2$, but I have no idea how to go about…
Cereal
  • 123
1 2 3
…
74 75