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
votes
1 answer

Can we define limiting behavior function of higher order in terms of norms?

Let $f(x):=x$ and $g(x):=x^{2}$, then we say that $f=\mathcal{O}(g)$ if there exists $\alpha,x_{0}>0$ such that: $$ |f(x)|\leqslant\alpha|g(x)| $$ for all $x>x_{0}$ My question is if now $f,g\colon \mathbb{R}^{n}\to\mathbb{R}^{n}$, defined by…
SPARSE
  • 442
-1
votes
2 answers

Calculate big-$\Theta$ for $T(x) = \log(x2x!)$

$T(x) = \log(x2x!)$ use the property of log, $\log(x2x!)$ is equivalent to $\log(2x) + \log(x!)$ My approach is to prove big-$O$ and big-$\Omega$ for $T(x)$,then big-$\Theta$ just follows. If I want to calculate big-$O$ and big-$\Omega$ for $T(x)$,…
user59036
  • 1,525
-1
votes
1 answer

Decay of time derivative

If a function $f(\vec{x}, t)$ goes to zero faster than $\frac{1}{|\vec{x}|}$, will $\frac{\partial f}{\partial t}$ always decay faster than $\frac{1}{|\vec{x}|}$ too? Assume that $f$ is differentiable.
Bio
  • 835
  • 6
  • 13
-1
votes
1 answer

Order of growth of a function involving the square root of the logarithm

I am trying to show that for $a \sqrt{\frac{\pi }{k}}>1$, and $k \geq 1$, $$\sqrt{k (k-1)} \sqrt{\log \left(a \sqrt{\frac{\pi }{k}}\right)} = O(k)$$ using the standard big O notation. I can see that the function is beneath a straight line of a…
apg
  • 2,797
-1
votes
1 answer

Does the master theorem apply for ≤ inequalities?

Does the master theorem specifically apply when the recurrence contains ≤, ie. $T(n) ≤ 4T(n/2) + n$ ? I cannot seem to find a definition containing inequalities.
Ben
  • 1
  • 1
-1
votes
1 answer

$g \in o(f)$ implies $f + g \in \Theta(f)$

Prove that $g \in o(f)$ implies $f + g \in \Theta(f)$. I'm pretty stuck on this one. I know that there is a constant $c_2$ such that $f \le c_2 (f+g)$, but I'm not sure how to prove that there exists a constant $c_1$ such that $c_1 (f+g) \le f$.…
Patrick Perkins
  • 9
  • 2
-1
votes
1 answer

proving big-Oh for a function

I have the following function, and I want to prove/disprove that it is $\Omega$(n$^2$): \begin{cases} 4[sum(n/2,n)],& \text{if n is even } \\ 2n-1+sum(n-3,n), & \text{otherwise} \end{cases} (it should be 2 n-1, so a space…
thenewomp
  • 3
-1
votes
1 answer

What is the average efficiency of this sorting algorithm?

I was following down a rabbit hole of math when I came up with a sorting algorithm. I try looking around the internet to see if anyone has come up with the same thing. It doesn't seem like it was the case (if anyone can prove me wrong, please tell…
ThePretzelMan
  • 352
-1
votes
1 answer

Property of 'little oh' notation from Tom Apostol Vol.1

How to prove that 1/(1+g(x)) = 1 - g(x) + o(g(x)). Moreover, what exactly does this equality mean in this particular case?
user516517
  • 11
-1
votes
2 answers

Asymptotes of function

How to find a if the function below doesn't have a vertical asymptotes. $f(x)= \frac{x^2-ax+2}{x-2}$
User14414
  • 23
-1
votes
1 answer

Prove or disprove $n^3/O(n) = O(n^2)$

Intuitive it feels like it should be proven, but I'm stuck on trying to prove, and I can't think of a way to disprove it either. To prove it, I need to show that (for one side): $n^3/O(n) = cn^2$ for all $n>n_0$ and exist $n_0>0$ and $c>0$. $\{…
Oren
  • 3
-1
votes
1 answer

Can the symbol $∈$ mean relation between elements?

Long time no see math concepts. but as I want to improve in programing I need to get into some math concepts and symbols for understanding time complexity. I saw this explanation in a problem that I solved: "Because of $h ∈ O(n)$, the space…
Nelssen
  • 101
-1
votes
2 answers

Big O notation Problems

I have read a lot of articles on Big O notation but never found a problem like this and I have no idea how to solve it. $$3 \cdot O(n^3) = O(3 + n^3)$$
NastyBlackLeg
  • 1
-1
votes
1 answer

Which function is faster $f_1$ or $f_2$

I'm trying to compare two functions asymptotically, are there any simple solution for this? $f_1(n) = 3n^2 + {\dfrac{100\log n}{\sqrt n}} $ $f_2(n) = 10 + \dfrac{2(n! - 5n)}{n^{3/2}} $ Which one is better?
syntax
  • 11
-1
votes
1 answer

Prove that $n^2= \theta(5n^2+n)$

i am trying to prove that $n^2= \theta(5n^2 + n)$ And i'm using this formula: $c_1(5n^2 + n) ≤ n^2 ≤ c_2(5n^2 + n)$ $\forall n ≥ n_0$ Is it true? If it's true could you please help me for find the c1,c2 and n0. I found them but i'm not sure are they…
syntax
  • 11
1 2 3
…
74 75