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

learn more… | top users | synonyms (1)

0
votes
1answer
70 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 ...
1
vote
2answers
87 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
1
vote
4answers
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
13
votes
2answers
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)$? ...
6
votes
1answer
85 views

How does the size of the set $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$ grow?

How does the size of the set $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ grow as a function of $R$? My try: It's clear that $|A(R)| ...
0
votes
1answer
30 views

Is $f(n)=\Theta(g(n))$ equivalent to the existence of the limit $\lim_{n \to \infty} \frac{f(n)}{g(n)}$?

Title pretty much says it all. I would think this should be true, but don't have much experience in this area of mathematics and don't know how to go about proving it.
0
votes
1answer
98 views

asymptote vs extraneous values

I am having trouble understanding the difference between a rational function with an asymptote versus having extraneous solutions. What is the difference between the two, if there is. Aren't ...
6
votes
2answers
87 views

Sufficient conditions to have $f' = O(f(x)/x)$.

Suppose $f$ a nonnegative real-valued function, non-decreasing, $O(x^m)$ for some $m \in \mathbb{Z}_{\geqslant 0}$ and $C^1$, with $f'$ being monotonic and nonnegative. Are this sufficient conditions ...
9
votes
1answer
136 views

Integral Asymptotics for inhomogenous phase

I'm looking for asymptotics for an integral of the form: $$F(n):=\int_{1/2-i\infty}^{1/2+i\infty} e^{\phi(n,z)}dz$$ where $\phi(n,z)=(n-n^3)\log(1-z)+n^2\log(1+z)-n\log(z)$. One can solve for the ...
2
votes
1answer
74 views

Asymptotic sequence of tan(z)

I have a question about the asymptotic sequence of $\tan(z)$: $$\tan z \sim ~ z+\frac{1}{3}z^3+\frac{2}{15}z^5 $$ $$\sim~ \sin z+\frac{1}{2}\left(\sin z\right)^3+\frac{3}{8}\left(\sin z\right)^5$$ ...
1
vote
2answers
55 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
0
votes
1answer
39 views

Why $\frac{1}{nh}O(h)=o[(nh)^{-1}]$ and $O_p(h^2+(nh)^{-1/2})=o_p(1)$

Suppose that we know: as $n\to\infty$, $h\to 0$ and $nh\to\infty$. Why does it follow that $\frac{O(h)}{nh}=o[(nh)^{-1}]$, $O_p(h^2+(nh)^{-1/2})=o_p(1)$? I'm learning kernel density ...
0
votes
1answer
44 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1}, \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
0
votes
2answers
72 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 ...
1
vote
1answer
137 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 ...
2
votes
2answers
113 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}$ ...
0
votes
1answer
222 views

Verify answers to these big o notation questions

May someone look over if I did these big o notation problems correctly? Some of them were tricky. 1) $f(x) = 10 = O(10)$ 2) $f(x) = 3x + 7 = O(x) $ 3) $f(x) = x^2 + x + 1 = O(x^2) $ 4) ...
2
votes
3answers
115 views

How does $\log(x^2 + 1)$ become $\log(2x^2)$?

My textbook attempts to take the big O of $\log(x^2 +1)$. It proceeds by saying $x^2 + 1 \le 2x^2$ when $x \ge 1$. But I don't know how it came up with this idea. Question: Why set $x^2+1$ to a ...
0
votes
1answer
53 views

Big-$\mathcal{O}$ notation for CRT and Extended Euclidean Algorithm

I am very unfamiliar with Big-$\mathcal{O}$ run time calculation. I know that for addition the run time is $\mathcal{O}(\log n)$ and for multiplication the run time is $\mathcal{O}(\log^2 n)$. How ...
3
votes
1answer
58 views

Asymptotic elementary expression for the antiderivative of $x^x$

It is well known that there exists no elementary function $f$ with $$\int x^x\,dx \quad = \quad f$$ Is there an elementary function $g$ such that $$\int x^x\,dx \quad \tilde{} \quad g$$ in the ...
0
votes
1answer
73 views

Big oh notation

I am learning big-oh notation and i am wondering if something like $O(\sqrt{x})=O(O(\sqrt{x}))$ is true, and, more importantly, how you can prove this rigorously using the definition of big-oh? ...
1
vote
0answers
41 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
36 views

Explain why $f = O(g)$ for $f(n) = (2^{n} + 2n^{2})^{1/5}$ and $g(n) = 4n^{5} + 8n + 2\log(n)$

I am working on a review for a test and I'm trying to figure out how to explain the following problem: Determine if the following statement is True or False. Briefly explain why: If $\,f(n) ...
1
vote
2answers
44 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 ...
1
vote
1answer
165 views

Define function F which is big O but not big theta

Searching for one definition of $f : \mathbb{N} \rightarrow \mathbb{N}$ with $f' : \mathbb{N} \rightarrow \mathbb{N} $ defined with $f'(n) := f(n+1) - f(n)$ with the bounderies $f=O(f')$ and $f ...
1
vote
0answers
38 views

Singularities of complex exponential and asymptotic expansion

Consider the equation $$L[u(x,t)] = \tilde u(s,t) = \frac{e^{-t\sqrt{s^2-1}}}{s-2}$$ I want to find $u(x,t)$ in the form of an integral. I first need to find the poles and singularities of the ...
1
vote
1answer
168 views

Growth of binomial coefficient

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest ...
2
votes
0answers
62 views

Asymptotic expansion of integral (Laguerre)

Consider $$L_n = \frac{1}{2\pi i } \oint_{C'} \frac{1}{(1-t)^{\alpha+1} t^{n+1}} e^{-\frac{xt}{1-t}} dt\,\,\,\,(1)$$ where $C'$ is an anticlockwise contour around zero. Now set $\alpha = n$ and I want ...
0
votes
2answers
33 views

Can a function exist that is both $o(g(n))$ and $\omega(g(n))$?

Can a function exist which is both $o(g(n))$ and $\omega(g(n))$? Wouldn't this imply $$m |g(n)| \le |f(n)| \le k |g(n)| $$ If $f(n) = g(n)$ then wouldn't an arbitrary integer $m$ be greater ...
5
votes
1answer
139 views

Estimating $\int_0^x f(x-t)f'(t)dt$

I'm attempting to estimate $\int_0^x f(x-t)f'(t)dt$ in terms of a simple asymptotic expression with an error term for some 'well-behaved' functions, namely $f = O(x)$, of class $C^1$ or higher, with ...
1
vote
1answer
77 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 ...
0
votes
0answers
61 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 ...
6
votes
1answer
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$?
3
votes
2answers
100 views

asymptotics of sum

I wanna find asymptotic of sum below $$\sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k$$ assume I know asymptotic of this sum (I can be wrong): $$\sum\limits_{k=1}^{n}\frac{1}{k}(1 - ...
2
votes
0answers
27 views

Asymptotic for degree [duplicate]

How can I find asymptotic for $\chi(n)$, if $\chi^{\chi^\chi} = n$. Is here self-qualification estimation? I tried to take the logarithm of both sides, but to nothing has come.
4
votes
1answer
124 views

asymptotic of $x^{x^x} = n$

How find the asymptotic behavior for $x(n)$ if $x^{x^x} = n$? I supposed that $x = O(\log\log{n})$ and took logarithm two times. So I get $x = O(\frac{\log\log{n}}{\log\log\log{n}})$ Is it right? ...
1
vote
1answer
84 views

Closed-form expression for a sum of reciprocals of factorials [closed]

Is there a closed-form expression for the finite sum $$\sum_{s=1}^{2^{n-1}}\frac1{(s-1)!}$$ as a function of $n$?
0
votes
0answers
38 views

Additive and Multiplicative Error in $n!$ Approximation

Let $S(n)=\sqrt{2\pi n}\big(\frac{n}{e}\big)^n$ be the approximation of interest to $n!$. What are good lower and upper bounds on the following two functions $$(1)\mbox{ }|S(n)-n!|?$$ $$(2)\mbox{ ...
2
votes
1answer
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 ...
4
votes
2answers
130 views

Laplace's method with nontrivial parameter dependency

I need to approximate the following integral using Laplace's method: $$ \int_0^{\infty} \frac{x^{\lambda} \lambda^{-x}}{(1+x^2)^\lambda} dx \\ = \int_0^{\infty} \exp\left(\lambda \log(x) - ...
0
votes
1answer
108 views

algorithmic complexity in Big O notation

Here is the function that is meant to be analyzed f1(n) 1 v ← 0 2 for i ← 1 to n 3 do for j ← n + 1 to 2n 4 do v ← v + 1 5 return v I was wondering if my ...
1
vote
2answers
69 views

Pitfalls/subtleties of $O$ notation

What are some examples of $O$ subtleties? I'm not only thinking of the asymmetry of the $O$ relation, but of the ways in which $O$ constants can depend on nearby parameters, and the fact that the ...
4
votes
1answer
68 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
9
votes
1answer
128 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
3
votes
2answers
143 views

Asymptotic development of a recurrent sequence

Let $u_0 = 1$ and $u_{n+1} = \frac{u_n}{1+u_n^2}$ for all $n \in \mathbb{N}$. I can show that $u_n \sim \frac{1}{\sqrt{2n}}$, but I would like one more term in the asymptotic development, something ...
0
votes
1answer
31 views

BigOh Complexity: $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$?

Show $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$ Can I do it like this? Since exponent rules/laws allow this: $\frac{x^{3} + 2x}{2x + 1}$ $=$ $\frac{1}{2}x^{2} + 2x$ Must show a constant c>0 and k ...
2
votes
1answer
127 views

Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.

Let $\gamma$ be the Euler-Mascheroni constant. In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log ...
2
votes
0answers
22 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 ...
0
votes
1answer
47 views

Asymptotic distribution of ratio / multiplication of two variables

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 ...
0
votes
0answers
34 views

Orders of growth of typical sequences

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ...