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

learn more… | top users | synonyms (1)

5
votes
1answer
50 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
21 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.
5
votes
0answers
46 views
+500

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 ...
50
votes
0answers
1k views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
0
votes
1answer
20 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 ...
5
votes
2answers
44 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 ...
2
votes
1answer
36 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
28 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
15 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
30 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 ...
9
votes
3answers
98 views

A series involving $\prod_1^n k^k$

Is this series $$\sum_{n\geq 1}\left(\prod_{k=1}^{n}k^k\right)^{\!-\frac{4}{n^2}} $$ convergent or divergent? My attempt was to use the comparison test, but I'm stuck at finding the behaviour of ...
-2
votes
0answers
38 views

Modifying recursion matching result

Let $f_0=\frac{1}{4}$ and $f_i=\dfrac{3f_{i-1}}{4}+\dfrac{2^{-i}}{2}$ and this gives $f_n>\frac{3^{n}}{4^{n+1}}$. This problem came as I was trying to solve a complexity theory problem. ...
2
votes
0answers
57 views

Bounding an implicitly defined sequence

I have a sequence $\lambda_0,\lambda_1,\ldots,$ which is defined implicitly as $$ \lambda_0 = \frac{1}{2},$$ and $$\lambda_{k+1} = \max_{\lambda\in[1,b]} \left\{\frac{1}{2\lambda}\prod_{0\leq ...
3
votes
1answer
60 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
0
votes
2answers
31 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 ...
0
votes
0answers
21 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
0
votes
1answer
51 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
36 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}$ ...
2
votes
3answers
105 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
23 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) ...
0
votes
1answer
36 views

Behavior of the following function at $x=0$ singularity

I am trying to do the following integral: \begin{equation} \int\frac{1}{x^{2p}(x-1)^{2q}}\,\mathrm dx \end{equation} for positive $2p$ and $2q$. I want to understand how does this function blow up ...
0
votes
1answer
23 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 ...
14
votes
2answers
697 views

Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$

How to show that $$\lim_{n\to\infty}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$ No clue at all. Need help! Appreciated!
3
votes
1answer
46 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 ...
30
votes
1answer
541 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
0
votes
1answer
45 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? ...
0
votes
1answer
28 views

Explain why $f = O(g)$

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
0answers
10 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 ...
1
vote
2answers
41 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
34 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 ...
0
votes
0answers
16 views

Using the WKB approximation to find the values of different positive Eigenvalues $E_n$

Consider $$y''(x)+EQ(x)y=0, Q(x)>0 \mbox{ subject to } y(0)=y(\pi)=0$$ The WKB approximation is (which i've proved) is: $$y(x) = CQ^{-0.25}(x)\sin{(\sqrt{E}\int_0^x\sqrt{Q(t)}dt)}$$ Then the ...
0
votes
0answers
12 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
42 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
40 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 ...
4
votes
1answer
72 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 ...
0
votes
2answers
25 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 ...
1
vote
1answer
23 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 ...
3
votes
2answers
71 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 - ...
0
votes
0answers
35 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
605 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$?
7
votes
3answers
170 views

Asymptotic for sum

How can I find formula for $\displaystyle{\sqrt[3]1 + \sqrt[3]2 + \sqrt[3]3 + \cdots + \sqrt[3]n}$ with an accuracy ${\rm O}\left(\, 1 \over \vphantom{\LARGE A}n^{5}\,\right)$ Is here we should use ...
2
votes
0answers
24 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.
0
votes
1answer
42 views

Growth function big theta

a) Show that $3x+7$ is $\Theta(x)$. b) Show that $2x^2 +x -7$ is $\Theta(x^2)$ $2x^2+x-7 \geq x^2$ for $x \geq 2$ if $x \gt 1$ $x^2 \gt x$ $2x^2 \gt 2x$ $x^2 \gt 1$ $x^2\geq x^2$ c) Show ...
4
votes
1answer
97 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? ...
2
votes
1answer
67 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 ...
1
vote
1answer
58 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$?
1
vote
0answers
32 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 ...
0
votes
0answers
27 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{ ...
3
votes
2answers
130 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 ...
2
votes
1answer
76 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 ...