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

Asymptote for double variable function

How can I find asymptote of the following function ? $y=x^{3}y^{2} - \sin(x)$ Is there a way except finding $y$ directly ?
Suman Samadder
  • 1
0
votes
0 answers

Asymptotic analysis of this statement.

Say if I have some expression $\frac{h}{k^2}$ or $\frac{h^2}{k}$ and I send both $h,k \rightarrow 0$. Can I say that the expressions tend to zero without further explanation? When we send these constants to zero are we sending them to zero at the…
user197848
0
votes
0 answers

Asymptotic representation of the function $\frac{a+bx^2\log(x)}{c-\log(x)+dx^2\log(x)}$

In computing an asymptotic expansion I have come across the term: $$\frac{a+bx^2\log(x)}{c-\log(x)+dx^2\log(x)},$$ where $a,b,c$ and $d$ are non zero constants, in general. I am unsure if to proceed to expand, using the geometric series expansion…
user385459
  • 345
0
votes
0 answers

Uniform asymptotic expansion of $F(a,n,x)$ as $n\to\infty$

Let $F(a,n,x)$ be a function defined as $$ F(a,n,x):={_2}F_2\begin{pmatrix}{\begin{matrix} 1, & an+2+ix \\ an+2, & an+3+ix \\ \end{matrix}} & ; -n \end{pmatrix}\\ $$ where $i=\sqrt{-1};a>1 \text{ and is fixed}$;$n\in\mathbb{N}$ and…
mike
  • 5,604
0
votes
0 answers

Asymptotic of a sum

How do I find asymptotic of $\sum_{i=1}^n i^k$. All I noticed is it is summation of inverse harmonic number.
lllook
  • 217
0
votes
1 answer

O-Notation: Understanding Limsup Definition

I think I understand the definition of the big-Oh notation as well that of the small-Oh notation. But I wonder about the limits. I understand that $ f = o(g):\quad\lim_{x \rightarrow a} \,\left|\frac{f}{g}\right| = 0 $ because f becomes…
omnesia
  • 101
0
votes
1 answer

asymptotic estimate of $\sum 1/(k^2 H_k)$ where $H_k$ is the harmonic series

I need some help here. I started with $$\sum_{k=1}^N \frac{1}{k^2 H_k}=\sum_{k=1}^N \frac{1}{k^2 \int_0^1\frac{1-x^k}{1-x}dx}=\sum_{k=1}^N \frac{1}{\int_0^1 k^2 \frac{1-x^k}{1-x}dx}$$ But I do not know how to continue anymore.
kylexy
  • 11
0
votes
0 answers

Theta notation, complicated proofs

Problem: To prove $$2n^2 2^n +n\log n=\Theta(n^2 2^n)$$ I initially started by trying to prove the upper bound, and the way I thought for doing this was by principle of mathematical induction, considering $$4n^2 2^n \geq 2n^2 2^n + n\log n.$$…
Ramit Sawhney
  • 3
0
votes
1 answer

asymptotics and calculating it

I have a task to show by definition that $\ln n^{2} + 1 = \Theta (\ln n)$ by definition , we know that we have to find c1 and c2 such as $c_{1} * \ln n<\ln n^{2} + 1 < c_{2} * (\ln n)$ we can find find c2 easily $\ln n^{2} + 1 < c_{2} * (\ln…
trolkura
  • 407
0
votes
3 answers

Prove that $f(n)$ is $O(1)$

Let $f(n) = \sqrt{n^2 + 100n} − n$. Prove that f(n) is O(1). I tried to solve this problem with the L'Hospital rule, but as I kept deriving, it just became a bigger mess and harder to simplify. Is there an easier way to solve this?
Jasmine
  • 67
0
votes
1 answer

Big O notation for two series

I'm having trouble understanding how to analyze these two series for their Big O representations. I can get the correct answer for this series $1+2+3+4+...+N$ is $O(N^2)$, which I found by finding the Big O for the equation $N(N+1)/2$. Apparently…
cdignam
  • 575
0
votes
0 answers

Asymptotic approximation of $M^{\theta}$ when $\theta \to 0$

I am unable to prove the following: $M^{\theta} \sim 1 + \log(M)\theta$ as $\theta \to 0$. Here, $M$ is a constant.
ksank43
  • 97
0
votes
1 answer

A function that is neither O(gi(n)) nor Ω(gi(n))

I have two functions $$g_1(n) = 1$$ $$g_2(n) = 10^{10^n}$$ I have to find one function that is neither $O(g_i(n))$ nor $Ω(g_i(n))$ ($i=1,2$). I already have : $$f(n) = 2 \sin (n)$$ That should be enough for $g_1(n)$, but I don't know how to come up…
ninesalt
  • 189
0
votes
1 answer

Show $n\log(n^2 + constant)$ is $\in \Theta(n\log n)$

As mentioned in the title, I have to show that $n\log(n^2 + 21) + 11\log(n) \in \Theta(n\log n)$. I am having quite a headache over trying to split the summation in $n\log()$ and I don't really know what to do. Any advice is much appreciated.
Clement
  • 101
0
votes
1 answer

Big O and running time of specific method given $\Theta(n)$ information on inner function

If evaluating $f(n)$ is $\Theta(n)$ i = 1; sum = 0; while (i <= n) do if (f(i) > k) then sum += f(i); i = 2*i; Would the running time of this be $O(nlogn)$ because i is doubled after each iteration and the function is…
MathIsHard
  • 2,733
  • 16
  • 47
1 2 3
…
74 75