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

learn more… | top users | synonyms (1)

20
votes
5answers
682 views

Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$

Suppose $n\in\mathbb{Z}$ and $n > 0$. Let $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$ I would like to find a Big O bound for $H_n$. A Big $\Theta$ result would be even better.
5
votes
4answers
243 views

What is the difference between analytic combinatorics and the theory of combinatorial species?

Yesterday I asked the question Why should a combinatorialist know category theory?, where Chris Taylor suggested me to have a look at combinatorial species. I had heard the term before but I haven't ...
0
votes
1answer
43 views

Show that $3^n = 2^{O(n)}$ [duplicate]

The formal description I have is that this is this: $f(n) = n^{O(n)}$ iff there exists some $h(n) = O(n)$ such that $f(n) = n^{h(n)}$. I don't see how this can be applied to the problem to show that ...
2
votes
2answers
50 views

Big O/little o true/false

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me. $2n = O(n)$: true $n^2 = O(n)$: false $n^2 = O(n\log^2 n)$: I ...
2
votes
1answer
44 views

Gaussian integral asymptotics

I am trying to derive the asymptotics of $$\int_{2\sqrt{m}}^{\infty}e^{-\frac{x^2}{4}}x^mdx$$ as $m\to\infty$ with no success. I tried integrating by parts, but could get no nice expression. Any help ...
0
votes
2answers
28 views

Sum of independent Bernoulli variables with parameter p which is also a random variable

I've read all the questions related to this, but I couldn't find an answer. We have n independent Bernoulli variables $X_i \in Be(p_i)$ where all the $p_i$ have the same distribution, let's say ...
2
votes
3answers
308 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
2
votes
1answer
57 views

From programming to mathematics

I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with ...
0
votes
2answers
32 views

Sum of a sum [algorithm design and analysis]

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ...
1
vote
0answers
29 views

Method of dominant balance and perturbation theory

We know perturbation theory express the desired solution of differential equations in terms of a formal power series in some "small" perturbation parameters: $y=y_0+\epsilon ^1 y_1+\epsilon ^2 ...
1
vote
2answers
37 views

Big O / Logarithmic Equivalency

In one of the algorithms textbooks I was reading, it states that $O(3^{\log_2n})$ can be rewritten as $O(n^{\log_23})$. Why is this the case?
0
votes
1answer
32 views

Asymptotic running time in Big Theta notation

If I have an algorithm with the running time $T(n) = 5n^4/100000 + n^3/100$, I know that I get Θ$(n^4)$. Now, if I have something like $T(n) = \frac{10n^2 + 20n^4 + 100n^3}{n^4}$, does this yield ...
0
votes
1answer
152 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
1
vote
1answer
26 views

Construct two functions based on big O constraint

I'm doing an algorithm problem goes like this. Construct two functions $f$, $g$ : $\mathbb{R}^+\rightarrow\mathbb{R}^+$ satisfying, $f$, $g$ are continuous; $f$, $g$ are monotonically increasing; ...
0
votes
1answer
45 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
1
vote
1answer
47 views

Asymptotic Relative Efficiency: Poisson

I'm trying to find the asymptotic relative efficiency of a Poisson process: $$\frac{\lambda^t \exp(-\lambda)}{t!} = P(X=t).$$ When $X = t = 0$, the best unbiased estimator of $e^{-\lambda}$ is ...
5
votes
1answer
50 views

Asymptotics of A030283

I wondered about the following sequence $a_i, i \in \mathbb N$ today: $a_1=1$ $a_n={\text{Smallest integer} > a_{n-1} \text{ that does not share any decimal digits with } a_{n-1}}$ The first ...
0
votes
1answer
129 views

A question about prime gaps

Recently, I have been reading the Wikipedia article about prime gaps (http://en.wikipedia.org/wiki/Prime_gap) and I came across the following: Hoheisel was the first to show that there exists a ...
0
votes
0answers
33 views

Asymptotic expansion of the floor function at infinity

Is it possible to study the behavior of the floor function at infinity by estimating its growth? The floor function has countably many discontinuities at integers, so I'm afraid that these ...
1
vote
1answer
53 views

Expansion of lower incomplete gamma function $\gamma(s,x)$ for $s < 0$.

The lower incomplete gamma function for positive $s$ is defined by the integral $$ \gamma(s,x)=\int_0^{x} t^{s-1} e^{-t} dt. $$ Taylor expansion of the exponential function and term by term ...
1
vote
1answer
36 views

Scaling a function with two 'asymptotes' of which one is non-constant

I have a bunch of curves that look roughly like the example below. Each curve has two 'asymptotes' a constant value for $x\rightarrow0$ and a linear curve for $x\rightarrow\infty$ (although, as in the ...
0
votes
2answers
35 views

Showing that $ { }_2F_1(1, n + 1;n+2; \frac{1}{2}) \in O(2^n)$

Is the following statement true? $$ { }_2F_1\left(1, n + 1;n+2; \frac{1}{2}\right) \in O(2^n)$$ What are the steps to prove it?
1
vote
2answers
88 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
4
votes
1answer
111 views

Asymptotic estimate of an oscillatory differential equation

Let $f\in C^1(\mathbb{R} ,\mathbb{R} )$ and satisfying the condition: $$ \forall x >0, \quad f(x)>0, \forall x<0 , \quad f(x)<0 $$ Let $(\alpha, \beta) \in \mathbb{R^2}$. ...
2
votes
1answer
32 views

Recurrence relation and big-O-notation

Consider the following recurrence relation: $$T(n)=c\cdot + 2\cdot T(n/2)$$ This is the recurrence relation for the Merge-Sort algorithm. How can one deduce from this equation the time complexity of ...
1
vote
0answers
49 views

How to find Laplace approximation for following integral?

Let's have integral $$ I(x) = \frac{1}{2\pi} \int \limits_{-\pi}^{\pi}e^{xcos(\theta )}d \theta, \quad x \to +\infty . $$ How to use Laplace approximation for this integral and find first two ...
1
vote
1answer
262 views

Laplace transformation of a polynomial function involving square root (or approximation of the integral)

Could somebody suggest how to solve this Laplace transform: $$ \int_0^\infty{e^{-at}\over\sqrt{A+Bt+Ct^2}}{\rm d\,}t $$ ? The real coefficients $A,B,C$ are chosen such that the roots of $A+Bt+Ct^2$ ...
0
votes
1answer
56 views

$\frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$ the same as $\frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$ for $n \rightarrow \infty$?

I need to show that $$ \frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$$ for some number $s$ is essentially the same (asymptotically negligible) as $$ \frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$$ as $n ...
0
votes
1answer
51 views

Equation with big O notation

Recently when I read a paper on Erdos's distinct distances problem, I met the following equation $$\dfrac{(mn-x)^2}{x}=O(m^{4/3}n^{4/3}+n^2)\quad\text{where $n\ge m$},$$ and the authors immediately ...
0
votes
0answers
27 views

Question about picking value large enough so that an inequality holds for all values larger than said value

This question makes me wonder about more general inequalities, but I have a particular example. Let $C$ be a positive fixed constant, $0<\epsilon<1$ be given, and assume $\alpha,\beta\in ...
2
votes
1answer
44 views

Big Oh and Big Theta relations confirmation

I just want to confirm these statements, I know that Big O, and Big theta, are partial order and equivalence relations respectively, all positive integers, but not sure on these restrictions. $f:N ...
0
votes
1answer
56 views

Perturbation theory for algebraic equations

I'm trying to find expansion (up to the 2nd non zero term) for the roots of: $x^5-x^2+\epsilon=0$ as $\epsilon\rightarrow0$ So I've assumed the solution may be written as a power series ...
4
votes
1answer
281 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
8
votes
2answers
164 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
0
votes
2answers
47 views

Understanding big O notation examples

I understand the main idea of big-O-notation, yet I have two questions regarding to the following examples: Prove/Disprove: 1. $2^{2n+1} = O(2^{2n})$ 2. $2^n = O(2^{n\over 2})$ Questions: I ...
1
vote
1answer
68 views

Solve $\epsilon x^3-x+1=0$

I'm trying to find the expansion for the roots of this equation. I've found one root as $x\sim 1+\epsilon $. Now considering the dominant balance I want to rescale so that $\epsilon x^3\sim O(x) ...
2
votes
1answer
38 views

Determining asymptotic behavior through generating functions

I need to determine the asymptotic behavior of $$a_n=\sum_{k=2}^{n-2}\frac1{\ln k\ln(n-k)}$$ as $n\to\infty$. I know some elementary methods that might help. For example, split the index $\lvert ...
0
votes
1answer
49 views

Counting function for sums of three squares

Legendre showed that an integer is the sum of three squares if and only if it is not of the form $4^n(8m + 7)$ for some nonnegative integers $n$ and $m$. However, I have been unable to find any ...
0
votes
2answers
27 views

Big O, Omega and Theta Exercises

i have a few exercises to do but i need someone to correct me if they can. I am very new to the Big O notation so please forgive me for being too basic. I need to represent everything under Θ. T(n) ...
0
votes
0answers
25 views

Master Theorem Exercise

Could you please help me with a master theorem equation i have? for master theorem we have T(n) = aT(n/b)+f(n) where a>=1, b>1 here i have: T(n) = 5T(n/4)+12 a = 5; b = 4 and f(n) = 12; Now is c = 0 ...
0
votes
1answer
40 views

Big O Notation Exercise

I'm having a small problem. I'm very new in this section so please bear with me. I understand Big O meaning what everything signifies like the O(n), O(n^2), O(x^n), O(log n) and O(1). I also learn ...
0
votes
1answer
32 views

Can asymptotic series include negative exponents (Laurent series)?

An series $\{a_n\}$ to a function $f(x)$ is defined as $$ f(x) - \sum\limits_{n=0}^{N} a_n x^n\sim a_{N+1}x^{N+1} $$ as $x \rightarrow x_0$ for all N. I have just heard, that the exponents $n$ do ...
1
vote
1answer
93 views

delta method question

Let $H:\mathbb{R}^k\to \mathbb{R}^k$ be measurable and differentiable at $x_0$, i.e. $$H(x) = H(x_0) + L(x-x_0) + o(x-x_0)$$ near $x_0$. Suppose $\{X_n\}$ and $X$ are random vectors in $\mathbb{R}^k$ ...
2
votes
1answer
70 views

Selberg's Symmetry Formula

I'm going through a proof of the Prime Number Theorem and the derivation of Selberg's Symmetry Formula. However, in it there is one step that is perplexing me. Would anyone be able to help explain why ...
1
vote
3answers
54 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
1
vote
0answers
26 views

Asymptotics for exponential integrals

Suppose I have a situation where I want to find an asymptotic expansion as $x \to \infty$ for an integral of the form: $$ \int_{a}^{b} f(t) e^{-\phi(t) x} \mathrm{d}t$$ Let us also suppose that ...
4
votes
1answer
185 views

Application of Riemann-Lebesgue Lemma

I am considering the integral $\int_a^{\infty}f(t)\cos(\omega t)dt$ and I want to find the asymptotic expansion using the Riemann-Lebesgue Lemma where as $\omega\rightarrow \infty$, $a,\omega$ real ...
1
vote
0answers
27 views

$\lim_{z \to x \pm i \infty} \Gamma(z) \zeta(z + \alpha) = 0$?

I guess $\lim_{z \to x \pm i \infty} \Gamma(z) \zeta(z + \alpha) = 0$ where $x$ and $\alpha$ are real numbers. The guessing is from numerical experiments and I know $\Gamma(z)$ vanishes exponentially ...
0
votes
2answers
39 views

Prove that $3^n=O(n^3) $ is not true

Prove that $3^n=O(n^3) $ is not true. I came up to $3^n \le cn^3 $ but can not go further, I guess I need to do log both side, But don't know
1
vote
2answers
75 views

Prove that $a^n$ is $O(n!)$.

I proved by induction that $2^n = O(n!)$. Can this fact be used to prove the following: Let $a$ be a positive constant and $n$ be a natural number. Show that $a^n=O(n!)$. I have already ...