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
151 views

How to differentiate an expression involving big-o notation?

From Apostol - Introduction to analytic number theory (Theorem 3.3) we have $$ x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}):=E(x), $$ I want to differentiate $E$ -- to get a rough ...
1
vote
1answer
63 views

Asymptotic behavior of the solution to an equation

Let $c\in(0,1)$ be a constant and let $k$ be a positive odd integer, and let $a(k)$ denote the value of $a$ that satisfies the equation $$(1-a)^kk\sqrt{a}=c$$. As $k\rightarrow\infty$, what can we ...
3
votes
2answers
126 views

Is there a closed form for $\sum_{j=1}^{n} j^2\log{j}$?

Question Is there a closed form for $\sum_{j=1}^{n} j^2\log{j} = 1\times0 + 2^2\times\log{2} + 3^2\log{3} + \dots + n^2\log{n}$? I'm trying to look for the simplest $\Theta$ notation. Attempt Let ...
0
votes
1answer
186 views

The order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$

Let $g(x)=0.5(x+a/x)$. Determine the order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$ toward $x=a^{.5}$. This is a problem in our homework in the class ...
3
votes
2answers
268 views

Algorithm for adding n 1-bit numbers

suppose adding two numbers, (that first number has a bits and second number has b bits) can be done in ...
1
vote
0answers
45 views

Using singularity analysis to find the main asymptotic term of the Catalan Numbers

Using singularity analysis to find the main asymptotic term of the Catalan Numbers \begin{align} C_n = [z^n]\frac{1-\sqrt{1-4z}}{2z} \end{align} Can someone please explain to me the general concept ...
1
vote
1answer
27 views

Find a power series expansion of $\frac{4x^2+2x}{1-3x-10x^2}$ about the point $x = \frac{1}{5}$

Find a power series expansion of $\frac{4x^2+2x}{1-3x-10x^2}$ Now I know that $\frac{1}{5}$ is a singularity of the $\frac{4x^2+2x}{1-3x-10x^2}$ and I know that $f(z) = ...
0
votes
1answer
99 views

Which case of the Master theorem applies to the recurrence $T(n)= 100T(n/99)+\log(n!)$?

How to use the Master theorem to solve $T(n)= 100T(n/99)+\log(n!)$? I was given this question, and I can't figure out which case of the master theorem goes here. Thanks for your suggestions.
0
votes
1answer
43 views

Lower Bound Omega Notation

I have to prove that some number $S$ is bigger than $\Omega(|V|)$, where |V| is the number of vertices. I read the definition of asimptotic notations, but I am still confused with the examples. Fot ...
1
vote
1answer
90 views

Question about efficiency of an algorithm (Big-O)

The efficiency of the algorithm dolt can be expressed as O(n)=n^3.Calculate the efficiency of the following program segment exactly and by using the big-O notation. ...
3
votes
3answers
303 views

Find a real entire function $f(z)$ asymptotic to $\ln(x^2+1)$ for real $x$.

Find a real entire function $f(z)$ asymptotic to $\ln(x^2 +1)$ for real $x$. More specific I want $f(0)=0$ and $\frac{1}{2} \ln(x^2+1) < f(x) < 2 \ln(x^2+1)$. Or prove it does not exist.
4
votes
1answer
103 views

Asymptotics on the largest prime for which $x^n+1\equiv y^n$ has no nonzero solution

It $\let\epsilon\varepsilon\let\leq\leqslant\let\geq\geqslant$is a well known result that for every $n\in\mathbb N$, $x^n+1\equiv y^n\pmod p$ is non-trivially solvable for sufficiently large primes ...
1
vote
1answer
66 views

Closed form for estimated sum with different asymptotic bounds?

I found asymptotic lower and upper bounds for a summation as follows: $$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_n f(n) \le 1 + O\left(\frac{1}{n}\right).$$ If you want to write it in a ...
0
votes
1answer
38 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
0
votes
1answer
98 views

What are sets and classes in maths, and how are they related to $O()$ and $o()$ notation?

Are there many definitions of sets and classes in mathematics, as given in Formal definion of the notations used in measuring time complexity? And in particular, why the notation given in Fedja's ...
0
votes
0answers
52 views

Big O evaluations

I'm confused about how to approach Big O problems. I'm presented two functions: $$f(n) = 4^{log_4n}$$ and $$g(n) = 2n +1$$ I simplified f(n) to: $$f(n) = n$$ Now I'm not sure how to compare f(n) ...
1
vote
1answer
422 views

Do small o, small omega, and big theta cover all relationships between two functions

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true: $f(n) \in o(g(n))$ $f(n) \in \omega(g(n))$ $f(n) \in \Theta(g(n))$ Logically, this makes sense to me. For a ...
0
votes
1answer
54 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
1answer
22 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
4
votes
1answer
99 views

Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
0
votes
0answers
337 views

Taylor series expansion and Laplace transform final value theorem

I cant figure out how some transformations are made in one article on physics. Here is expression in s-domain and they want to find its asymptotic value. $$ \xi(s) = \nu_1(s+1)=\frac{1}{(s+1)} ...
0
votes
1answer
52 views

Confusion with Big-oh

So, big-oh means: for at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a So let's evaluate the statement $1 = ...
2
votes
0answers
58 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
5
votes
0answers
134 views

Boundary Layer, leading order, Pertubation Theory, Differential Equations

I have got the following problem, taken from Multiple Scale and singular perturbation methods, Kevorkian & Cole book, page 94, exercise 1.b.: Find the leading order of the problem: $\varepsilon ...
1
vote
3answers
267 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
1
vote
0answers
108 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
1
vote
1answer
109 views

Is 1/x the “slowest” asymptotically falling off differentiable function?

As a physicist, I tend to think about $\sim 1/x$ as the "slowest" fall-off of a "reasonable" function. Let us state this formally: $${\rm lim}_{x \to \infty} f(x) = 0, f(x) \in Reas \implies \exists A ...
1
vote
0answers
20 views

Showing that $\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$

I'm currently making my way through Dixon's paper 'The Probability of Generating the Symmetric Group'. (It can be found here.) In the proof of lemma 3 it is asserted that ...
1
vote
1answer
44 views

Proving that $ \frac{1}{n}\int_{-\infty}^{\sqrt{n}w}k(v/\sqrt{n})\phi(v)dv$ is $O(n^{-1})$

Suppose that $h:\mathbb{R}\to\mathbb{R}$ is infinitely differentiable. Define \begin{equation} k(w)=\left\{ \begin{array}{ll} \frac{d}{dw}\left(\frac{h(w)-h(0)}{w}\right)&w\neq 0,\\ ...
1
vote
1answer
80 views

Switching Limits and summation

I'm currently working on proving some theorems and there is one recurring problem that I somehow can't solve. $a_n$ is a real sequence in either $[0,1]$ or $\mathbb{R}$ that approaches $0$. ...
1
vote
1answer
64 views

How to rigorously simplify an expression with Big-Oh Composed within another Big-Oh.

I am trying to show the following: $$ O(e^{n(\cos n^{-2/5}-1)}) = O(e^{-Cn^{1/5}})$$ The problem I'm having is I'm trying to get a hang of asymptotic notation, and I can't quite figure out how to ...
1
vote
1answer
58 views

Asymptotics of logarithm: $\frac{1}{n}\ln(a+o(1)) = \frac{1}{n}\ln(a)+o(\frac{1}{n})$

I am having problems with the use of the little oh notation my professor is adopting in the solutions to some exercises. As an example I do not understand why $$ \frac{1}{n}\ln(a+o(1)) = ...
1
vote
1answer
34 views

Lower bound on $F$ under the assumption $\theta F(s)\le sF'(s)$

Let $F(s)=\displaystyle \int_0^{s}f(t)\,\mathrm dt$. We suppose that there exists $\theta>2$ such that $\theta F(s)\le f(s)s$ for all $s\in \mathbb{R}$ and that $F(s)>0$ for all ...
0
votes
1answer
427 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
1
vote
0answers
39 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...
1
vote
1answer
55 views

Can I prove this, or hopeless? Deviating too much from mean

Can I prove this: We have a sequence of vectors $\left(X_i(n)\right)$ for $i=1,\ldots,t$, where $n\rightarrow \infty$. $t$ does depend on $n$ and is Chosen such that $1 \ll t \ll n$, for instance, ...
0
votes
1answer
25 views

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$ Do you use the fact that $\pi(t) = \frac{t}{\log t} + O\left(\frac{t}{\log^2t}\right)$ and then $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt= ...
0
votes
1answer
40 views

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$? Would you use $\lim_{x\to \infty}\frac{\pi(x)\log(1-\frac{1}{x})}{\frac{1}{\log x}} = 1$? and how would you show this? Can you ...
1
vote
0answers
69 views

How to show an aymptotic expansion is uniformly valid?

I have an equation $$ nt = u - \epsilon \sin(u) $$ which asks for the first four terms in the asymptotic solution. Hence if the solution is $u_0 + \epsilon u_1 + \cdots.$, expand $\sin(u)$ around ...
0
votes
0answers
27 views

Approximate $_2F_1(a,b;c;x)$ for large (maybe negative) values of $a, b, c$?

I need asymptotic approximations of the Hypergeometric function $_2F_1(a,b;c;x)$ for large positive values of $a, b, c$. Specifically, I need approximations for all the possible regimes, in which one ...
2
votes
0answers
35 views

Incomplete Beta function $\text{B}_x(\alpha,\beta)$ approximation for large $\alpha,\beta$?

I need good asymptotic approximations to the incomplete Beta function $\text{B}_x(\alpha,\beta)$ for large values of $\alpha,\beta$. Specifically, I need approximations valid for the following ...
0
votes
1answer
27 views

For which function $f$ is $1 \ll \sum_{i=1}^{n} i \cdot i^{-f(n)} \ll n$?

I am interested in the expected value of a power-law Distribution. I would like to let the Parameter $f(n)$ depend on $n$ for $n \rightarrow \infty$. And now I would like to determine $f(n)$ such ...
0
votes
1answer
263 views

How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$ which happens to be $O(n^2)$ complexity. How do I now prove that: $$a = n/2$$ is a tight upper bound for this relation? I have been ...
2
votes
1answer
44 views

Closed-form term for this expression

I have a normal Distribution $X \sim N(\mu, \sigma)$. Is there an easy way to give an asymptotic estimate with small error (I would prefer with relative error $\rightarrow 0$) for $P[X \geq k]$? We ...
0
votes
2answers
288 views

How to prove that $n^{1.1} \not\in O(n(\log n)^2)$

This is a problem from a university exam: True or false: $n^{1.1} \in O(n(\log n)^2)$. The solution says False, but I'm unable to prove it. I tried using the limit test for Big-O: $\lim_{n \to ...
2
votes
1answer
31 views

$f(t) = \cos t^{-1} + \int_t^\infty \frac{1}{\tau^2 + f(\tau)^2} d\tau$ implies the integral is $O(\frac{1}{t})$

The following is a quote from "asymptotic methods in analysis" by de Bruijn (p. 136). If we know that the real function $f(t)$ satisfies the relation $$f(t) = \cos t^{-1} + \int_t^\infty ...
2
votes
1answer
95 views

Difference between $\lim P[…]$ and $P[ \lim ]$

In a Galton-Watson branching process the extinction probability is sometimes given by $$\lim_{t \rightarrow \infty} P[X(t)=0]$$ and sometimes as $$ P[\lim_{t \rightarrow \infty}X(t)=0]$$ Is there a ...
2
votes
0answers
92 views

asymptotic expansion of the integral for large tau

How can I proceed to resolve this integral? $$ c_1\int_{-\infty}^{\infty}{\frac{\cos\left(x\tau\right)}{\left(1 + c_{2}\,x\right)^{\alpha}}}\, \,{\rm d}x $$ where $c_1, c_2$ are positive constants, ...
2
votes
2answers
103 views

Growth Rate of Alternating Sign Matrices

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$ This sequence counts the number of $n\times n$ alternating sign matrices: ...
1
vote
2answers
48 views

Asymptotic behaviour of $\prod_{p \leq x} (1 + 4/(3p) + C p^{-3/2})$

I'm reading Montgomery and Vaughan and in it they state quite simply \begin{equation} \prod_{p \leq x} \left(1 + \frac{4}{3p} + \frac{C}{p^{3/2}} \right) \ll (\log x)^{4/3} \end{equation} as $x ...