# Questions tagged [asymptotics]

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

6,237 questions
Filter by
Sorted by
Tagged with
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 ...
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.)
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)}$ ...
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$ ...
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 ...
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,...
27 views

25 views

105 views

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
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} ...
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 ...
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 ...
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 ...
38 views

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 ...
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})$?
### 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{...
### 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 ...