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

How is $\left(1+\mathrm{O}\left(\mathrm{N}^{-1 / 3}\right)\right)^{-1}$ equal to $\left(1+\mathrm{O}\left(\mathrm{N}^{-1 / 3}\right)\right)$?

In the book of Concrete Mathematics by Graham, Knuth, Patashnik, at page 453, it is given that $$ \begin{aligned} \lfloor\mathrm{N} / \mathrm{K}\rfloor &=\mathrm{N}^{1-1 / 3}\left(1+\mathrm{O}\left(\mathrm{N}^{-1 /…
Our
  • 7,285
0
votes
1 answer

Does $\Theta(n^{-1}) = \Theta(1)$?

Does $\Theta(n^{-1}) = \Theta(1)$? I'm pretty sure that this is true for $O$, but not about $\Omega$ and $\Theta$.
scand1sk
  • 323
0
votes
0 answers

Find a Big-O Notation for following recurrence formula : $T(n) = T(2/5n) + T(3/5n) + O(n\log n)$

I think it will be $T(n)=O(n^2)$. This is because... Suppose $T(n) \leq cn^2$ Then $T(n) \leq c\cfrac{13}{25}n^2+O(n\log n) \leq cn^2$ ($\because$) $there\ \ is\ \ a\ \ positive\ \ c\ \ such\ \ that\ \ O(n\log n) \leq c\frac{12}{15}n^2 $ Am I…
alsrbok
  • 1
0
votes
0 answers

Solving a challenging asymptotic equation

Suppose we have the asymptotic $$ R \sim 1 - \sqrt{\frac{2t}{\beta}} + \frac{1}{\beta}\left[ \frac{V}{\sqrt{\pi}} \sqrt{kt} - \frac{2}{3}(1+kV)t + \mathcal{O}(t^{3/2}e^{-1/kt}) \right] +\mathcal{O}(\beta^{-3/2}) \tag 1$$ as $t \to 0^+$, and $\beta…
Cornelius
  • 347
0
votes
3 answers

Finding the asymptotes of the trajectory of a point parameterized by $(x,y)=\left(\frac{t}{1-t^2},\frac{t-2t^3}{1-t^2}\right)$ for $t\geq 0$

Let $(x,y)$ be Cartesian coordinates in the plane and suppose a moving point has coordinates $$x=\dfrac{t}{1-t^2}, \quad y=\dfrac{t-2t^3}{1-t^2}$$ at time $t\ (t\geq 0)$. Describe the trajectory of the point and find asymptotes. Solution: I…
RFZ
  • 16,814
0
votes
0 answers

asymptotic behavior of $y'= \sqrt{-a/y^2+by^2-cy^4+d}$ at x=infinity?

Asymptotic behaviour of $y'= \sqrt{-a/y^2+by^2-cy^4+d}$ at x=infinity ? Boundary condition is given by $y'(\infty)=0$ I can find the solution numerically but I cant find the asymptotic behaviour analytically, any help ?
ODE
  • 29
0
votes
1 answer

Looking for a way to find the proportional growth rate in time for any given notation

I am wondering if there is a straight forward way to illustrate the proportional growth rate in time (or space) for any given notation such as $O(n^2)$ or $O(logn)$? My initial thought is that $O(n^2)$ would be equal to $O(n)*O(n)$ but I'm sure…
Switchkick
  • 103
0
votes
2 answers

Growth of $()$ satisfying $t(n)=2^nt(n/2)+n^n$

$t(n)=2^nt(n/2)+n^n$ I can't use Master Theorem becaus $2^n$ and althought I am familiar with other Recursive Tree method, I can't solve it. Is there a chance solve it using Recursive Tree method?
Furkan Ergün
  • 1
0
votes
1 answer

Why $O(\epsilon^{-1})\ll O(\epsilon^{-3/2})$

When looking for the approximate roots of $\epsilon^2x^6-\epsilon x^4-x^3+8=0$, since this is a single perturbation problem, we need to track down the three missing roots, so we consider all possible dominant balances between pairs of terms as…
user71346
  • 4,171
0
votes
1 answer

How to get $e^{\sqrt{\log (x)}} \leq e^{log(x)}=x \leq x^n$?

Hi i was browsing through various asynptotic questions and got stuck in the mid due to the following daubt in the answer given in the link: Prove that $e^{\sqrt{\log x }}=O(x^n)$. How beni got: $$e^{\sqrt{\log (x)}} \leq e^{\log(x)}=x \leq x^n?$$
nikhil
  • 103
0
votes
1 answer

How did they prove this big o inequality

I was reading my textbook when I came across this example I was wondering how they got 35n^3 since we have log(n)?
Turkey
  • 25
0
votes
2 answers

An estimate for required $n^{\alpha}\ge \ln(n^2)$

I am trying to find an estimate in terms of $\alpha\in(0,1)$ of how large $n$ should be so that the below inequality is satisfied for all large $n$. $$ n^{\alpha}\ge \ln(n^2)$$ Is there a good way to go about this?
GA-Student
  • 171
0
votes
0 answers

Conditions needed to ensure that the asymptotic order of a function and of its derivative are the same

Let $f(x)$ be a real valued and continuously differentiable function. Suppose that $f(x) = \mathcal{O}(g(x))$ in the sense that there exists a positive real number $M$ and a real number $x_0$ such that $|f(x)| \leq M g(x)$ for all $x \geq x_0$. Let…
user304347
  • 43
0
votes
2 answers

How to prove the following O-notation?

$f(n)=O(g(n))$ and $f(n),g(n)>0$ for $n ≥ 1$, then there is a constant c such that $0 ≤ f(n) ≤ c·g(n)$ for $n ≥ 1$
jack90
  • 3
0
votes
1 answer

$A$ is in $\Theta (n \log n)$ and $B$ is in $\Theta (2^n)$ - $B$ can not be more efficient than $A$?

Now suppose that $A$ is in $\Theta (n \log (n))$ and $B$ is in $\Theta (2^n)$. Is it always possible that $B$ is more efficient (asymptotically) than $A$? I think the answer is no, but I am not sure how to prove it. Can you help me at this point?…
Leo
  • 97
1 2 3
…
74 75