Questions tagged [asymptotics]

Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

Filter by
Sorted by
Tagged with
2
votes
0answers
24 views

Solving the recurrence: $𝑇(𝑛)=9𝑇(𝑛^{1/6})+\log^2(𝑛)$ [duplicate]

I need to solve the following function using recurrence, $$𝑇(𝑛)=9𝑇(𝑛^{1/6})+\log^2(𝑛)$$ I know for a fact that this is done by making a change of variable but can someone tell me how to go about ...
-2
votes
1answer
27 views

oblique asymptotes of $x^3+y^3=3axy$ [on hold]

How do I find the oblique asymptote of the function $x^3+y^3=3axy$. And please explain and generalize the method that you are using. (We were taught a method but, we were not given the reasoning.)
0
votes
1answer
13 views

Asymptotic equivalence-like relation

Let $f, g: \mathbb R\to (0,\infty)$ such that $\cfrac{f(x)}{g(x)}$ is bounded both from below and above for all $x\in\mathbb R$. Is there any name for this relation? (Like if $\cfrac{f(x)}{g(x)}$ ...
0
votes
2answers
14 views

Proof of inequalities (relating to Big O notation)

Question: Prove that $n \leq (\frac{n^3}{n^2+2})^c$ for all non zero positive integer $n \geq n_0$ and some positive non zero constant $c$. (This is relating to the Big O proof) Attempt: let $c=2$ ...
3
votes
1answer
40 views

Explicit bounds for $x_n + e^{-x_n} \geq x_{n+1} \geq x_n +e^{-x_n} - \frac{1}{4}e^{-2x_n}$

Let $(x_n)$ be a positive, increasing sequence such that $x_1 = \gamma$ (the Euler constant), and for all $n\geq 1$ $$x_n + e^{-x_n} \geq x_{n+1} \geq x_n +e^{-x_n} - \frac{1}{4}e^{-2x_n}.$$ I would ...
2
votes
2answers
77 views

Asymptotic behaviour of a counting function

I was studying a proof of Prime Number Theorem from Stein's Complex Analysis: Theorem: Let $\pi(x)$ be the prime counting function. Then $$ \pi(x) \sim \frac{x}{\log x}. $$ The proof makes sense,...
0
votes
0answers
27 views

Big-O notation, logs vs exp

I have simplified these functions to the best of my ability. I know logs are less than exp, but are all exponential functions greater than logs, even if the power is less than 1? $$n^{1.01} = \Omega(...
-3
votes
0answers
28 views

Function that is Big-O but not little-O [on hold]

Is it possible for $f(n)$ and $g(n)$ to not be the same function and still be $f(n) = O(g(n))$ but $f(n)!= o(g(n))$?
0
votes
1answer
15 views

Based off of asymptotic growth, why would this statement be true: lg^100(n)= o(n^0.01) ? Would it be because any log is less than any exponential?

Based off of asymptotic growth, why would this statement be true: lg^100(n)= o(n^0.01)? Would it be because any log is less than any exponential?
1
vote
0answers
22 views

Estimation of $\sum_{n\leq x}|\mu (n)|* \mu$

Let $\mu$ be te Moebius function. The question is: Use the Riemann hypotesis to prove that $\sum_{n\leq x}|\mu (n)|* \mu<<_{\epsilon}x^{\frac{1}{4}+\epsilon}$ I know that the drichelet series of ...
1
vote
0answers
29 views

Riemann's method for asymptotic formulas

This is the text of the exercise: Let $\mathbb{C+}$=$\{a+ib\in\mathbb{C}|a>0\}$ and $\mu_{_F}(a)$ the Lindelof function of $F$. Let $F(s)=\sum_{n\geq1}\frac{a_n}{n^s}$=$\frac{4}{s-1}+\frac{1}{...
0
votes
0answers
21 views

Asymptotic Complexity: Valid Strategy for Simplifying Summations?

In one of my discrete math classes, I recall my professor mentioning that a general rule for simplifying summations when computing asymptotic complexity is: "multiply the summand by the quantity (...
1
vote
2answers
57 views

$1/y -\log y = x $, asymptotically

I'm interested in the asymptotic expansion for $x \rightarrow +\infty$ of the solution to $$ \frac{1}{y} - \log y = x $$ Is the leading term simply $y \sim 1/x$? How to show that rigorously? How ...
1
vote
0answers
16 views

Proof of asymptotic relation $\sum_{i=1}^n i^k = \Theta(n^{ k+1} )$

I'm doing an exercise to proof that $\sum_{i=1}^n i^k = \Theta(n^{ k+1} )$ I proved that $\sum_{i=1}^n i^k = O(n^{k+1})$, but I can't prove that is $\Omega(n^{k+1})$ I'm trying to do it by ...
0
votes
1answer
30 views

Time complexity of an iterative function related to bits

I am wondering about correct answer to this task from a test earlier today: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of ...
4
votes
1answer
148 views

Closed form of asymptotic behaviour of $\sum_{k=1}^n \sin(\sqrt{k})$

Motivated by the studies of convergence of various series of trigonometric fuctions with non trivial arguments which reached a peak in the sophisticated proof that $\sum_{k=1}^\infty \frac{\sin{n^k}}{...
0
votes
0answers
18 views

How can I show the arithmetic mean is O(1/n)?

Particularly the sample mean, which I think should be $O(1/n)$, no? The definition I have says, $f(n)$ is of constant order ($O(1)$), when there exist some non-zero constant $c$ such that, $$\frac{f(...
1
vote
0answers
25 views

Expected value of the positive part of partial sum of random variables

Supoose $X_i, i = 1,2,..., T$ are i.i.d. nonnegative random variables. Given any constant $c > 0$, can I prove the following? $$\mathbb{E}[\sum_{t=1}^T(Tc - \sum_{k=1}^t X_i)^+] - \sum_{t=1}^T(Tc -...
0
votes
3answers
26 views

If $f$ is big or little oh of $g$, what can we say about $a^f$ and $b^g$ for $a,b>1$?

I’m interested in what operations preserve asymptotic relationships. For example, I can prove that if $f=o(g)$ (as $x\to\infty$), then $a^f=O(b^g)$, for any bases $a,b>1$. But I think that’s ...
5
votes
1answer
96 views

Maximizing the number of $n$-tuples in $\{1,…,m\}^n$ such that . . .

This question is motivated by the pattern of data obtained in my answer to the question $\qquad\;\;$The best $n$-digit password? I'll restate some definitions . . . For positive integers $m,n$ with ...
1
vote
1answer
38 views

Expectation of the “truncated” partial sum of random variables

Suppose $X_i, i = 1,2,..., N$ are i.i.d. nonnegative random variables. Given any constant $C > 0$, can I prove the following? $\mathbb{E}[\sum_{n=1}^N(C - \sum_{k=1}^nX_i)^+] - \sum_{n=1}^N(C - \...
-2
votes
0answers
16 views

Limiting Distribution of Estimator [closed]

If $\{X_n\}$ are i.i.d with $E(X_i)=0 $, $\text{Var}(X_i)=\sigma^2$, $E[(X_i-\mu)^3]$, and $ E[(X_i-\mu)^4]=\alpha$, then what is the limiting distribution of $\sqrt{n}\frac{\bar{X}}{\frac{1}{N}\...
-2
votes
0answers
12 views

Prove or Disprove by giving values of $n_0$ and $c$

$n \log_2(n)+n^2 \in \omega(n)$ (little-omega) Using Formal definitions. Is this the right way to prove it? $n \log_2(n) +n^2 > n^2 \ \forall n>0$ Choose $n_0 = 0$ i.e $n>0 $ and $c = ...
1
vote
1answer
49 views

prove or disprove: if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$

I'm trying to prove (or disprove) that if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$ but with no success. Can someone help me with this? thanks.
0
votes
1answer
49 views

$T(n) = 3T(n/2) + n$ — why does this series not diverge?

I'm trying to use a recursion tree to solve the recurrence $T(n) = 3T(n/2) + n$. After drawing out the tree, I can simplify the time formula to $$ T(n) = n(1 + \frac{3}{2} + \frac{3^2}{2^2} + \dots + ...
6
votes
1answer
105 views

Asymptotic behavior of $f(n)$ when $n\to\infty$

I want to know a tighter bound for the growth rate of $f(n)$ when $n\to\infty $, where $$ f(n)=\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n [\mathrm{lcm}(i,j)\le n][\mathrm{lcm}(j,k)\le n][\mathrm{lcm}(i,k)...
-1
votes
1answer
13 views

Prove or disprove: $n^{\log_2 n} = \Omega(n^b)$ for all $b > 0$

Prove or disprove: $n^{\log_2 n} = \Omega(n^b)$ for all $b > 0$ I have tried taking the limit. I know that if $\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$ then $f(n)=\Omega(g(n))$. Is it correct ...
0
votes
0answers
30 views

Prove or disprove: $n^{\log_2 n} = \mathcal{O}(a^n)$ for all $a > 1$

I am not sure how to solve this problem: Prove or disprove: $n^{\log_2 n} = \mathcal{O}(a^n)$ for all $a > 1$ I have tried calculating $\lim_{n\to\infty} \frac{n^{\log_2 n}}{a^n}$ to see if it ...
0
votes
1answer
15 views

Will the definition of big $O$ be equivalent to the one where we exchange the $n \ge N$ condition with $\forall n$

If we delete from the big $O$ definition the "$\exists N > 0$ such that $\forall n \ge N$" part and leave only the "$\forall n$" will the new definition be equivalent to the original one for $N \to ...
0
votes
1answer
31 views

Asymptotic behavior of equation$ O(n\log n)=O(n^{1.1})$

The following equation should be true: $O(n\log(n))=O(n^{1.1} )$ Based on the following article, one should see the equation as the left part being an element of the right part. What are the rules ...
0
votes
1answer
31 views

If the matrix $A_t = O(t)$ how can we say $A_T^{-1} = O_(1/t)$?

I have a matrix that is a linear combination of symmetric square matrices: $$A_t = \sum_{j = 1}^{i - 1} (t_j - t_{j - 1}) B_j + (t - t_{i - 1}) B_i$$ Here $t_j > t_{j - 1}$ and $t_{i - 1} \le t \...
2
votes
2answers
81 views

Large $n,k$ asymptotics for Stirling numbrs of the first kind $\left[ \matrix{n\\k}\right]$

$\left[ \matrix{n\\k}\right]$ is the notation for Stirling numbers of the first kind. This is the number of distinguishable ways to break$n$ objects into $k$ cycles. (Warning - Mathematica's ...
-1
votes
1answer
37 views

Tail estimation for $\int{\cos\sqrt{x}}\cdot \frac{1}{x}dx$

How to prove or disprove $$\int_x^{+\infty}{\frac{\cos\sqrt x}{x}}dx \leq\frac{K}{\sqrt{x}}$$ as $x$ goes to $+\infty$.
-2
votes
1answer
35 views

Equivalent of $\tan(\frac{\pi}{2x+1})$ in zero

My task is to find the equivalent of $$\tan\left (\frac{\pi}{2x+1}\right )$$ in zero. I tried using the formula $\tan(x)\sim x$ in zero, and got $\frac{\pi}{2x+1}$ and then this is $\sim\pi$ in zero. ...
0
votes
2answers
32 views

Limit of function with taylor series

I am trying very hard to understand the limits with the help of taylor expansion but i still stuck in it , $$\lim _{x\to 0^+}\left(e^{\frac{x^2-1}{x}}\right)$$ if I apply the taylor expansion $$1+\...
0
votes
1answer
18 views

Find time complexity (Big O) and (Omega)

for i:=1 to n do j:=2; while j<i do j:=j^4; end end I looks like while loop will have (log i)/(4*log(j)) iterations
0
votes
0answers
20 views

Large-$N$ asymptotics of solutions to certain recurrence relations.

Let $b \ge 0$ and let $a_+ \ge b$, $a_- \ge b$. Now, let $N \ge 1$ and $M \ge 0$ be positive integers. In addition let $0 \le n \le N$ and $x\in(0,1)$. We define following quantities: \begin{eqnarray} ...
0
votes
0answers
34 views

Exercise on Little “o”

I am working on asymptotic behavior of a function and this is the question i came ; $$f(x)=\lim _{x\to 0^-}\left({e^{\frac{x^2-1}{x}}}\right)$$ it can be solve with simple limit chain rule but how ...
0
votes
0answers
41 views

Find the intersection points of two asymptotic functions

I'm trying hard to find the intersection points of two asymptotic functions, in order to figure out at what exactly n coordinates, one function surpasses another. $y(n)=8n^2$ $g(n)=64n\lg n$ to ...
0
votes
1answer
57 views

Two dimensional recursion $f(x,y) = 0.5 f(x-1,y) + 0.5 f(x, y-1)$ solution or asymptotics

I have the following recursion relation and boundary conditions: $$f(x,y) = \frac{1}2 f(x-1,y) + \frac{1}2 f(x,y-1)$$ $$f(x,0) = x$$ $$f(0,y) = 0$$ Where $x$ and $y$ are non-negative integers. Does ...
1
vote
1answer
38 views

What is the error of asymptotic relation of large order behavior of Bessel function

The NIST Handbook of Mathematical functions eq. 10.19.1 [ref] gives for the asymptotic behavior of the Bessel function $J_\nu(z)$ for large real order $\nu\to\infty$ for fixed argument $z$ as $$ J_\...
1
vote
0answers
20 views

Show order of function

Let function $f$ that depends on parameter $h>0$ with $$f(x;h)=x e^{-\frac{x}{h}}, x>0.$$ I want to show the following: For fixed $x>0$ and for each $n \in \mathbb{N}$ we have $f(x;h)<...
0
votes
1answer
23 views

Series in negative powers

I want to find the asymptotic series of $g(x)=\frac{1}{x-1}, x>1$ in negative powers of $x$ while $x \to +\infty$, i.e. the sequence of coefficients $c_0, c_1, c_2, \dots$ such that $g(x) \sim c_0+\...
0
votes
0answers
38 views

Strogatz Exercise 4.3.9: Alternative derivation of scaling law

So, I have a problem with an assignment from Strogatz's "Nonlinear Dynamics and Chaos" book: (Alternative derivation of scaling law) For systems close to a saddle-node bifurcation, the scaling ...
0
votes
1answer
77 views

Integrate Gaussian$\times$Log

Show that $$\int_1^\infty e^{-\frac{x t^2}{2}}\log(t) dt \sim \frac{e^{-\frac{x}{2}}}{x^2}$$ for large positive $x$. I tried Taylor expanding the log. Each of the resulting terms can be ...
0
votes
0answers
20 views

Determine the dominant asymptotic behavior of function

The Bessel function $J_1$ is the bounded solution of the differential equation Bessel $x^2y''+xy'+(x^2-1)y=0$ at the point $0$ and gets the integral representation $$J_1(x)=\frac{1}{2\pi}\int_{\pi}^{\...
27
votes
1answer
609 views

Could these polynomials be identified?

Looking a good approximation of the $n^{th}$ positive root of the equation $$\color{blue}{\tan(x)=k x}$$ As already done many times, I expanded as Taylor series around $x=(2n+1)\frac \pi 2$ and used ...
1
vote
1answer
56 views

How to say something is $O(\sqrt{\log n})$ in word?

When something is $O(\log n)$ we say it's logarithmic in $n$. How can we say it in "word" when something is $O(\sqrt{\log n})$?
0
votes
0answers
34 views

Error term in Taylor approximations of $\sin$ and other series with zero derivatives of higher order

The taylor polynomial of many functions has a skip term due to the fact that some derivative of the function is 0, $f^{(i)}(a) = 0$. For example, the sine function can be written as follows: $$\text{...
1
vote
1answer
70 views

Prove or disprove: if $f(n)= o(g(n))$ and $h=\omega(1)$ then, $f(h(n))= o(g(h(n)))$

Prove or disprove: if $f(n)= o(g(n))$ and $h=\omega(1)$ then, $f(h(n))= o(g(h(n)))$ ive tried to approach it with limits calculation, but no matter which arguments I used the equation seems to be ...