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

learn more… | top users | synonyms (1)

1
vote
0answers
37 views

How to find the influence function of $\int_{[0,t]}(1-F_\_)^{-1}dF$,i.e., cumulative hazard function

The common strategy is to replace $F$ with $(1-t)F+t\delta_x$ and then expand the integral. However, I am not sure how to deal with $F_\_$. It seems different from $F$.
8
votes
2answers
662 views

Approximation of Products of Truncated Prime $\zeta$ Functions

The problem arose, while I was looking at products of power prime zeta functions $$ P_x(ks)=\sum_{p\,\in\mathrm{\,primes}\leq x} p^{-ks}, $$ with $k\in \mathbb{N}$ and $s=it$ with real $t$. By using ...
0
votes
1answer
197 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
-1
votes
1answer
419 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
0
votes
1answer
80 views

How to define theta in terms of omega and O?

I am trying to prove some logical stuff using the definitions of BIG O, BIG Theta and BIG Omega. Unfortunately I am a bit confused. And how can we represent Θ in terms of of those other notations? ...
3
votes
2answers
143 views

Show $S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}$ is $O(t^p)$ at zero

An old qualifying exam problem: For $t>0$, define $$S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}.$$ Show that $S(t) = C t^p + o(t^p)$ as $t\to 0$ . Find $C$ and $p$. There are a couple of ...
0
votes
2answers
70 views

If $f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or any other one-line relation?

$f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or $$\lim_{x \to \infty}[f(x)/g(x)]=1$$ where f(x)=pi(x)(prime counting function) and g(x)=li(x)(logarithmic ...
1
vote
0answers
38 views

Simplifying products

Sorry for the very general title, but I don't even know how to name my question. I got a formula which is: $f(n)=\prod_{i = 0}^{\infty} ((n \; \mathrm{rem} \; p^{i + 1}) \; \mathrm{div} \; p^i + 1) ...
1
vote
0answers
23 views

parametric integral and asymptotic representation

Here is a parametrial integral $$I(a)=\int_0^{\pi}\int_0^{\pi} ...
1
vote
1answer
41 views

Is $O(n \log n)$ always smaller than $O (m)$ for $n-1 < m < n^2$?

I am writing an algorithm that needs to finish in $O(m)$. The problem is for a graph $G( V, E )$, where $m = |E|$ and $n = |V|$. $m$ can be in the range of $n-1$ to $n^2 - 1$. If I do some ...
0
votes
2answers
48 views

Algorithm Analysis on Recurrence Relation.

Consider the following recurrenc relation: $f(n) = f(n/2) +nlogn$ Since this does not honor the form of the Master Recurrence, we need to obtain an estimate of the asymptotic order of $f$. According ...
0
votes
2answers
35 views

Prove $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$

Prove that $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$ I started this proof by trying to use induction, although as I put in $n=1$, although this gives: (when $n=1$) $1000.0002<2$ This is clearly untrue ...
1
vote
0answers
51 views

How to prove that $\sum_{p \leq x} {\log p \over p} = \log x + O(1)$? [duplicate]

Problem Prove that $$ \sum_{p \leq x} {\log p \over p} = \log x + O(1) $$ as $x \to \infty$. Notes: $p$ ranges over primes, $\log$ is natural Progress Using Riemann-Stieltjes integration and ...
26
votes
3answers
612 views

Expected length of the shortest polygonal path connecting random points

$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
2
votes
0answers
181 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
1
vote
0answers
78 views

Integration by parts in vector calculus

I have an axi-symmetric integral (the domain and all functions are axi-symmetric) in cylindrical coordinates which needs to be integrated by parts for use in a finite element code. The integral is ...
5
votes
4answers
3k views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
1
vote
1answer
27 views

Big O notation question of Kolman's book

If $$f(x) = x^{100} , g(x) = 2^x. $$ Show that $f(x)$ is a big $O(g(x))$, but $g(x)$ is not big $O(f(x))$.
0
votes
1answer
47 views

Does $ \log(x)^{x^a}$ eventually dominate $x^k$?

Does $ \log(x)^{x^a}$ eventually dominate $x^k$ for all $a\gt 0$ and for all positive integers $k$? And if so, how does one prove this? Thanks a lot for your help.
13
votes
4answers
397 views

Asymptotic formula for $\sum_{n \le x} \frac{\varphi(n)}{n^2}$

Here is yet another problem I can't seem to do by myself... I am supposed to prove that $$\sum_{n \le x} \frac{\varphi(n)}{n^2}=\frac{\log x}{\zeta(2)}+\frac{\gamma}{\zeta(2)}-A+O \left(\frac{\log ...
2
votes
1answer
305 views

Derivative of big O symbol

Let's only work with functions $f(x)$ that have a series expansion at $x=0$. Is it true that: $$ {d O(1)\over d x} = O(1) $$ for all such functions $f(x)$? Here $O$ is the big-O notation and we are ...
1
vote
3answers
62 views

Show $f(x) = (x^4+x^2+1)/(x^3+1) $ is $O(x)$

How would I find the witnesses $C$ and $k$ such that $f(x)$ is $O(x)$? What I tried was $$(x^4+x^2+1)/(x^3+1) ≤ (x^4+x^4+x^4)/(x^3+x^3) = (3/2)x $$ for values $x>1$. $C = 3/2, k = 1$ Is this ...
4
votes
2answers
192 views

Asymptotic behavior of $\sum_{n>x} \frac{\log n}{n^2}$

There is a well-known question that seeks the asymptotic behaviour of this function, for $x\geq 2$: $$\sum_{n\leq x} \frac{\phi(n)}{n^2}.$$ See, for example, Apostol "Introduction to Analytic Number ...
2
votes
1answer
66 views

asymptotic approximation when $a\to 0^+$ of $I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$

I want to find an asymptotic approximation when $a\to 0^+$ for the integral $$I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$$ I found the following approximation: $$C_1\, a\, \mathrm{ln}(1/a) ...
1
vote
1answer
77 views

Nesting big-O with big-Omega $O(g(\Omega(h(n))))$: is it $O$ for all $\Omega$ or for one $\Omega$?

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in ...
4
votes
2answers
118 views

how to find the asymptotic expansion of the following sum:

I need to determine an asymptotic expansion when $q \rightarrow 1$ of the sum $$S(q)=\sum_{n=0}^{\infty} \frac{q^n}{ (q^n + 1)^2 }.$$ Numerical computations suggest that $S(q)\sim\frac{c}{|q-1|}$ ...
5
votes
1answer
216 views

Obtaining the Airy kernel from the Christoffel-Darboux formula with asymptotic Hermite polynomials

Let the Kernel associated to a family of orthogonal polynomial $p_n(x)$ with weight $w(x)$ be defined as $$K_N(x,y):=\frac{\sqrt{w(x)w(y)}}{\int w(x) p_{N-1}(x)p_{N-1}(x)dx} ...
2
votes
1answer
110 views

Lommel function

I need to do this integral: $$\int_0^\infty dx\cdot x \sqrt{x^2+1}K_0(ax)$$ where K is the modified Bessel of second kind. I have seen that in Gradhsteyn 7th edition in 6.565.7 says that this ...
0
votes
2answers
39 views

Show Time $T(n) = Θ(n^3)$

I have to show that : $$T(n) = Θ({n^3})$$ We have this recursive function : $$T(n) = 8T(n/2) + n^2, n>=2$$ also we know that $$T(1) = 1$$ And it says that there is a "replacement method" to ...
1
vote
1answer
123 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
2
votes
0answers
46 views

The characterization of asymptotic dimension

Let X be a metric space. The following conditions are equivalent (a)asdimX = n (b)n is the smallest integer such that for every R > 0 there exists n + 1 families Ui i=0,1,2,...,n, and S > 0 such ...
2
votes
1answer
201 views

Master Theorem when B is a fraction.

So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball $T(n) = 4T(3n/4) + n^4$ Now I used my usual steps of listing out what A, B, ...
1
vote
1answer
53 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
1
vote
1answer
91 views

An integral relating to Bernoulli polynomials

Show that $$\int_{0}^{1}B_{2n+1}(x)(\cot({\pi}x)-2\sin(2{\pi}x))dx{\sim}0$$ where $B_{2n+1}(x)$ is the Bernoulli polynomials.
4
votes
1answer
111 views

Bernoulli number type asymptotics

I find an interesting formula but I can not prove it. Show that $$I_n=(-1)^{n+1}\int_0^1 B_{2n+1}(x)\cot(\pi x) \, dx\sim\frac{2(2n+1)!}{(2\pi)^{2n+1}}$$ where $B_n(x)$ is the Bernoulli Polynomials.
1
vote
1answer
57 views

Asymptotic equality proof with $a_n^2 \ln a_n ~ n$

Given $a_n^2 \ln a_n \sim n$, prove that $a_n \sim \sqrt{\frac{2n}{\ln n}}$. How do I approach this?
3
votes
1answer
87 views

Asymptotic behaviour of e * !n - n! , n tends to infinity

What is the asymptotic behaviour of the function $e !n-n!$ , where $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ is the subfactorial of $n$. I tried Wolfram Alpha but the series for n=$\infty$ is ...
2
votes
2answers
224 views

Asymptotic expansion of an integral

I came up with a simpler example which illustrates the technical difficulty I have encountered in my work. Consider an integral depending on parameter $\epsilon$: \begin{equation} ...
1
vote
0answers
51 views

Steepest descent?

Here I would like to see the behavior of a function as an integral when its argument (which is a parameter in the integral) goes to zero. If I try to evaluate an integral ...
2
votes
2answers
78 views

Proof that asymptotic density $>1/n$ implies every sufficiently large integer is the sum of $n$ terms

Gerry Myerson commented on a previous question, which at the time asked for proof that every integer is a sum of two deficient numbers, "The deficient numbers have natural density strictly greater ...
0
votes
1answer
44 views

Power Series Expansion Asymptotics

From my text: Given $\cos^n(x),$ set $x=\frac{\omega}{\sqrt{n}}$, then a local expansion yields: $\displaystyle\cos^n(x)=e^{n\log\cos(x)}=e^{(-\frac{\omega^2}{2}+O(n^{-1} \omega^4))}$ ...
2
votes
1answer
163 views

How do you simplify this big O sum?

I saw someone interpret $\sum_{i=1}^{n}\mathcal{O}\left(i^{k-2}\right)$ as $\mathcal{O}\left(n^{k-1}\right)$. Is this right? If so, can you explain?
0
votes
1answer
27 views

Asymototics of a real sequence in a Riemann sum

Let $t<0$ and $f(k)\in O(|k|^{t})$ a real function, $k\in\mathbb{Z}$. We consider $$a_n\cdot \sum_{k=1}^n \frac{1}{n} \frac{f(k)}{n^t}$$ where $a_n\subset \mathbb{R}$ and ...
3
votes
1answer
223 views

Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$

I need to find the asymptotic approximation of this sum $$\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$$ Can you please share a link to theory or hint how it can be solved? Here is my attempt $n ...
0
votes
1answer
108 views

Conditions for $o(|u|^{-1})$ decay of the Fourier transform of a bounded variation function

As the question suggests I am looking for a (not very restrictive) condition on a function of bounded variation so that its Fourier transform is $o(|u|^{-1})$ as $|u| \to \infty$. Let me elaborate on ...
2
votes
2answers
31 views

Growth of series with decreasing numerators and increasing deonimators

It is known that $$H(n)=1+\dfrac12+\ldots+\dfrac1n$$ grows with the same rate as $\log n$. Therefore, $$nH(n)=n\left(1+\dfrac12+\ldots+\dfrac1n\right)=\frac n1+\frac n2+\ldots+\frac nn$$ grows with ...
4
votes
1answer
92 views

Asymptotics of coefficients in the expansion of $\log\cos x$

Let $c_n$ be the coefficient of $x^{2n}$ in the Maclauren expansion of $\log\cos x$. What can be said about the asymptotics of $c_n$ as $n\to\infty$? I expect that this question is routine, but I ...
3
votes
0answers
89 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
1
vote
0answers
72 views

Boundary layer method

I am trying to solve the following differential equation using boundary layer method. $\psi ''(z) + \frac{1}{z} \psi'(z)(3 - \frac{4}{1+(\frac{z}{zc})^8})+ \frac{m^2}{1+(\frac{z}{zc})^8}\psi(z)=0$ ...
0
votes
1answer
43 views

Big Oh and Big Omega clarification

Can I get an explanation of: Can g(n) be Big O of $n^{2}$ and also the Big O of $n^{3}$? (at the same time) Can g(n) be Big Omega of $\Omega (n)$ and also be the Big O of $n$?