# Tagged Questions

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

91 views

### Approximate solutions for quintic equation

The other day I asked a question in here about deriving the equations $$u^2\left(\left(1-s_1\right)+3u+3u^2+u^3\right) =\alpha\left(s_0+2s_0u+\left(1+s_0-s_1\right)u^2+2u^3+u^4\right),$$ where ...
38 views

56 views

### Notation for asymptotic approximation

I was reading Stirling's approximation and got quite confused with the idea of asymptotic formula. So in Wikipedia it says that a function $F(n)$ of $n$ is asymptotic formula for $P(n)$ if $P(n)$ is ...
30 views

### Mutual Asymptotic analysis of the given fucntions

$f(n)$ = $3n^{\sqrt{n}}$ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n!$ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I ...
128 views

### A function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$

Determine a function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$? I don't know to satisfy these conditions.
43 views

1k views

### How does adding big O notations works

can someone please explain how adding big O works. i.e. $O(n^3)+O(n) = O(n^3)$ why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still ...
110 views

### Asymptotics of $\prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right)$

I am trying to work out the large $n$ asymptotics of $$S_n = \prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) .$$ ...
86 views

### Asymptotic behavior of $\sum\limits_{k=1}^n \frac{1}{k^{\alpha}}$ for $\alpha > \frac{1}{2}$

As the title states, I'm interested in the asymptotic behavior of $$\sum\limits_{k=1}^n \frac{1}{k^{\alpha}} , \alpha > \frac{1}{2}$$ for $n \to \infty$. Any hints/ideas?
117 views

### Limit of $\sqrt[n]{(x+1)…(x+n)} - x$ as $x \to +\infty$

Let $n \in \mathbb{N}^{\ast}$. I want to determine the following limit : $$\lim \limits_{x \to +\infty} \sqrt[n]{(x+1)\ldots(x+n)} - x.$$ Let $x = \frac{1}{t}$ with $t \to 0$. It is equivalent to ...
211 views

### Is there a function thats not in Big O and not in Big Omega?

I've been thinking about this problem for a while now but I can't fully come up with an example. It would make sense that this would exist and the only way I think it would work is if the functions ...
99 views

### Is there an “interesting” function that grows faster than $n^{kn}$ but slower than $2^{2^n}$ — relates to understanding googolplex

Motivation: I'm looking for some sort of convenient fact I can use to grasp the size of a googolplex. For a googol we observe a convenient one; it's very nearly equal to 70!. But for a googolplex I ...
14 views

### General or specific property? $(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$

As told in the title, I found this equality: $$(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$$ and wonder whether this is true in general or whether it does only hold in the context I've seen it. It comes ...
42 views

346 views

### Strict upper and lower bounds of a sum (Big-Theta)

I am trying to find a function f(k) such that $S_k=\sum_{n=1}^{k^2-1}(\lfloor\sqrt{n}\rfloor)=\Theta(f(k))$. What I have done so far: Ignoring the floor asymptotically we get: ...
37 views

### Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
139 views

### Can one apply a WKB method to an inhomogeneous first order differential equation in order to find the asymptotic expansion of the solution?

Consider $$\varepsilon \frac{dy}{dx} = Q(x)y + R(x)$$ where $\varepsilon$ is a small parameter. Can one apply a WKB method to find an asymptotic expansion for the ...
817 views

### Arrange in increasing order of asymptotic complexity

I have to arrange the above time complexity function in increasing order of asymptotic complexity and indicate if there exist functions that belong to the same order. So, my answer is $[lg(n)]^2$ ...
Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...