# Tagged Questions

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

72 views

### Time complexity and Stirlings approximation

We have an operation that is $O(\sum_{i=1}^{n^2}\log(i))$. Is this valid?: $= O(\log (n^2!)) = \{\text{Stirling}\} = O(\log((n^2)^{n^2})) = O(n^2 \log(n^2)) = O(n^2 \log(n))$ If so, what's an '...
95 views

### How to prove the gaussian functions are linear independent?

Assume that I have N Gaussian functions with different means $\mu_i$ and variances $\beta_i$, How to prove $e^{-\beta_i(x-u_i)^2}$ are linear independent? 1$\le$i$\le$N
67 views

### Why do we have $u_n=\frac{1}{\sqrt{n^2-1}}-\frac{1}{\sqrt{n^2+1}}=O(\frac{1}{n^3})$?

Why do we have $u_n=\dfrac{1}{\sqrt{n^2-1}}-\dfrac{1}{\sqrt{n^2+1}}=O\left(\dfrac{1}{n^3}\right)$ $u_n=e-\left(1+\frac{1}{n}\right)^n\sim \dfrac{e}{2n}$ any help would be appreciated
327 views

### $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$.

Let $f\in\mathcal{C}^2(\Bbb{R},\Bbb{R})$ be a positive function such that $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ does it implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$? ...
86 views

73 views

### Big $O$ estimate of $(n\log n+1)^2+ (\log n +1)(n^2+1)$

Give the Big $O$ estimate of $(n \log n +1)^2 + (\log n +1)(n^2+1)$ Taking big $O$ of the first function (ignoring constant and exponent), ($n\log n + 1)^2$ we get $O (n \log n)$ Taking big $O$ of ...
140 views

### How to solve a recurrence relation such as $T(n) = 2T(\frac{n}{2}) +$ $\frac{n}{\log (n)}$?

Wikipedia says that the equation cannot be solved using Master's Method. The equation matches with Master's Theorem except for $\frac {n}{\log(n)}$. A youTube tutor (seek time 11:42) solves this ...
125 views

### Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$.

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$. Since $2^n$ < $2^{n+1}$, you can say $2^{n+1}$ is not $O(2^{n})$ Since $2^n$ is < $2^{2n}$, you can say $2^{2n}$ ...
230 views

45 views

### For what sequences $a_n$ does the sequence $(1+\alpha a_n)^n$ converge?

We know $(1+\alpha/n)^n \rightarrow e^{\alpha}$ when $n\rightarrow +\infty$. Suppose we are given a modified version of the problem: $$\quad (1+\alpha\cdot a_n)^n \tag{1}$$ The question ...
173 views

84 views

### Asymptotics of a sum of scaled multinomial coefficients

I'm interested in finding the asymptotics of the following (for $p \in [0,1]$) $$\sum_{k=1}^{\lfloor (n-1)/2 \rfloor} \frac{k {n-1 \choose 2k} {2k \choose k}} {4^{k}p^{k}}.$$ The central binomial ...
62 views

### Algorithm to efficiently compute$A^k$

If a symmetric matrix $A$ has SVD $A=U\Sigma U^{\top}$, then $A^k=U\Sigma^kU^{\top}$. What would be the most efficient algorithm to compute $A^k$ such that the worst case time complexity is as low as ...
622 views

### Given two real sequences that go to infinity, is it possible to select two subsequences that grow at the same rate asympotically?

Given two positive real sequences $a_n$ and $b_n$ that both diverge to infinity, is it possible to choose two subsequences $a_{s_n}$ and $b_{t_n}$ such that $a_{s_n}/b_{t_n}\rightarrow1$?
100 views

84 views

### When is a particular sum $\Theta(n)$?

Define $$S_n = \prod_{x=1}^{\lceil\frac{n}{\ln{n} }\rceil} \left(\frac{1}{\sqrt{n}} + \frac{2x}{n}\left(z_n-\frac{1}{\sqrt{n}} \right)\right) .$$ I am trying to work out necessary and sufficient ...
136 views

23 views

### Strategies for approximating fourier transform of $k$-th power of the $n$-th derivative of a function

For a function $f(x)$ with Fourier transform $\hat{F}(q)$, I'm interested in understanding the relationship of the Fourier transform of a power of a derivative of $f$ to $\hat{F}(q)$. Explicitly, I ...
Suppose $\rightarrow_D$ denotes convergence in distribution. If we know $$f_1 \rightarrow_D W_1$$ $$f_2 \rightarrow_D W_2$$ Can we say something about the convergence of  f_1 f_2 \...