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
1answer
109 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
2answers
621 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 ...
0
votes
1answer
42 views

How would I find the big $\Theta$ of the following function?

$$f(n) = \frac{n}{\log(n)}$$ I understand the basics of how to find big O, Ω, and θ, however this particular function is giving me a lot of grief. To be more clear, I will give a simple example ...
2
votes
0answers
59 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 ...
1
vote
3answers
97 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
39 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
44 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
3
votes
1answer
104 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
2answers
84 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 ...
0
votes
1answer
23 views

Big O comparison

If $T(n) = \mathcal{O}(n^3)$ Then $T(n) = \mathcal{O}(n^2)$, is this statement right? Same question for omega, if $T(n) = \Omega(n)$ does that mean $T(n)= \Omega(n^2)$?
0
votes
0answers
17 views

What parameter settings make this expression $\Omega(1)$?

I feel a bit silly for asking this, but here goes... I have the expression: $$(1 - (1 - n^{c+d-1})^{n^{2d}})^{n^{2-2d}}$$ We can assume $d$ is a constant somewhere in the range $[0, \frac{1}{3}]$. ...
1
vote
1answer
62 views

Proofs of Asymptotics

I'm going through a few proofs to make sure I understand them and in two of the proofs, there is a step I don't understand. 1) In the first, we have that $f(x) = g(x) + ln\left(\frac{\lfloor x ...
4
votes
1answer
125 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}$. ...
4
votes
1answer
173 views

Stationary phase method for $\int_{-\infty}^{\infty}f(t)\exp(ix(t^3-t))dt$

I am currenty struggling with the integral $\int_{-\infty}^{\infty}f(t)\exp(ix(t^3-t))dt$ where $f(t)$ is smooth and $f\rightarrow 0$ as $t\rightarrow +-\infty$. I want to obtain the leading ...
4
votes
1answer
253 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 ...
2
votes
1answer
91 views

Help Obtaining an Asymptotic for $\sum_{n=1}^{m-1}\ln(n)\ln(m-n)$

How can I obtain an asymptotic for this partial sum, with an error term of at most $O(m^{1/2}\ln(m))$: $$\sum_{n=1}^{m-1}\ln(n)\ln(m-n)$$ I tried flipping the order of summation half way through to ...
1
vote
1answer
55 views

Big-O: Prove that d^n = O(n!)

Suppose constant d>0. Prove d^n = O(n!) left to right prove only, is there any way to prove that other than using limit?
0
votes
2answers
36 views

Quick Running Time Question

I have a quick question about some running time stuff. In my algorithm I run merge sort twice, then loop $n$ times. If this is the case, does this make sense? $\Theta(nlogn+nlogn+n) = \Theta(nlogn)$. ...
0
votes
1answer
57 views

Proving Upper Bound for Two Variable Function?

The question is: Prove (logn)^k = O(n) for every k>=1. I have never encounter a problem for proving an upper bound for two variables, so I am perplexed as to ...
2
votes
2answers
72 views

Big O with cosine?

Consider the functions $f(n) = n\cdot \max(0,\cos(\pi n))$, $g(n) = n$. What is the relation between these functions in big-$\mathcal O$ notation? Assume $n$ takes on only positive integer values. For ...
0
votes
2answers
87 views

Big O for modular exponentiation?

I am reading the Algorithms textbook by Dasgupta, Papadimitriou and Vazirani. To compute x^y mod N for large values of x y and N, they state: "To make sure the numbers we are dealing with never grow ...
0
votes
1answer
54 views

Asymptotic Expansion of Bessel $\frac{1}{\pi}\int_0^{\pi}e^{x\cos t}dt$

My question is how to find the asmyptotic expansion of $I(x)=\frac{1}{\pi}\int_0^{\pi}e^{x\cos t}dt$ as $x\rightarrow\infty$. I already got the expansion of $\int_0^{\pi/2}e^{-x\sin^2t} dt$ by using ...
3
votes
1answer
210 views

Asymptotic expansion of $\int_0^{2\pi}ae^{x\cos a}da$

I want to find the first two leading terms of the expansion of $\int_0^{2\pi}ae^{x\cos a}da$ Well in $[0,2\pi]$ $\cos a$ has has maxima $0,2\pi$ so I rewrite the integral to ...
4
votes
0answers
74 views

Asymptotics for Mertens function

It seems that the cumulative mean of the Mertens function is very similar in behaviour to $x$ raised to the power of the first zeta zero. I tentatively notate it as: ...
0
votes
1answer
40 views

A complex integration problem

The problem is: Let $\gamma$ be the circle of radius $R$ centered at $0$. Let $m$, $n$ be positive integers. Prove that, as $R$ goes to infinity, $\int _\gamma\frac{z^m}{z^n+1}dz=O(R^{m+1-n})$. And ...
2
votes
1answer
219 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 ...
0
votes
0answers
76 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
1
vote
0answers
39 views

Question about asympotic expansions!! please help!

Question: Find the constants $$a_0, a_1, a_2$$ in the asympotic expansion $$\int_0^x t\sqrt{ln(t)} dt$$ = $a_0(x^2)(lnx)^\frac 12$ + $a_1\frac {x^2}{(lnx)^\frac 12}$ + $a_2\frac {x^2}{(lnx)^\frac ...
3
votes
2answers
81 views

Asymptotics of coefficients

This is a question that asks the reader for a $strategy$ to solve a particular problem. I cannot solve this problem myself so I am looking around for general methods one might use to confront it with. ...
0
votes
1answer
87 views

Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
3
votes
0answers
77 views

Which series of numbers effectively translates the factorial to the exponential function?

We have the relation of the Bernoulli numbers $$B_{2n} = (-1)^{n+1}\frac {2(2n)!} {(2\pi)^{2n}} \left(1+\frac{1}{2^{2n}}+\frac{1}{3^{2n}}+\cdots\;\right).$$ For $n>1$, the right hand sum ...
0
votes
1answer
265 views

Time efficiency of brute force algorithm as a function of number of bits?

This is homework help so advising how to solve such a problem is appreciated. The question reads as follows: What is the time efficiency of the brute-force algorithm for computing $a^n$ as a ...
2
votes
2answers
122 views

How to determine growth rate of coefficients of generating function

For a given ordinary generating function $f(x)=a_0+a_1x+...$, are there any methods to determine the growth rate of its coefficients based on that of $f$ ? In particular if we are given the extra ...
0
votes
1answer
86 views

Asymptotes of $\Gamma(\frac{1}{2} +ix)$ when $\vert x \vert \to \infty$

I am currently looking for finding behaviour of the function $\vert \Gamma(\frac{1}{2}+ix) \vert$ when $x$ tends to $\infty$. I think I need to use the Stirling's approximation but I don't see how. ...
0
votes
1answer
21 views

BigOh - How to determine the upper bound dealing with eccentric series?

I would like to know what is the way to determine the upper bound of a series in BigOh terms. For example, suppose the following series is given: 2 + 6 + 10 + 14 + ..... + ((4 * n) - 2) How can I ...
1
vote
1answer
437 views

Asymptote of a parametric equation (with Arctan)

I need to find the asymptotes of a parametric equation. My book says you have a vertical asymptote when $y\to \infty$. But the parametric equation is the following: $$x= \frac 13t^3-\pi,y= \frac ...
3
votes
2answers
74 views

Asymptotic expansion of $\sum_{k=0}^{\infty} k^{1 - \lambda}(1 - \epsilon)^{k-1}$

I'm seeing a physics paper about percolation (http://arxiv.org/abs/cond-mat/0202259). In the paper the following asymptotic relation is used without derivation. $$ \sum_{k=0}^{\infty} k P(k) (1 - ...
1
vote
1answer
435 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
4
votes
1answer
63 views

asymptotics of inverse function

Suppose $f:[0,\infty)\to [0,\infty)$ is strictly increasing with $f(0)=0$ and it's given explicitly as a combination of elementary functions. How do you find the asymptotics of $f^{-1}(x)$ as $x\to 0$ ...
1
vote
2answers
131 views

How does big-O notation relate to the actual error involved in a numerical differentiation?

Suppose I have some position data ${x_1, x_2, ... x_n}$ that was sampled at an interval $h$. If I wanted the velocity data, I could apply a finite difference scheme: $ v_1 = \frac{x_2 - x_1}{h} + ...
4
votes
0answers
91 views

Prove that a series is $O(t^a)$.

Consider the series $$ u(t,x) = \sum_{i \geq 1} {u_i(x) t_1^i } + \sum_{i+2j \geq k+2, j\geq 1} {\varphi_{i,j,k}(x) t_1^i t_2^j y^k} $$ where $t \in \tilde{\mathbb{C} \setminus \{ 0 \}}$, $x$ is ...
2
votes
0answers
36 views

Asymptoticity of a definite integral

friends! I read on a book that, for $\alpha>1$, "being $g$ continuous in 0 [really $g$ is continuous in $[0,1]$, if it were useful to know] and approaching the extremes of the integral 0 for $n\to ...
0
votes
1answer
40 views

Ordering Equations Using Small-oh Notation.

I have a couple questions about this problem: Order the following functions $h_i$, for $1 \leq i \leq 5$, with respect to relation $f \prec g$ defined by the small-oh notation as follows: $f \prec ...
0
votes
1answer
93 views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that ...
4
votes
0answers
65 views

prime zeta function when $0<s<1$ [duplicate]

I would like to know if there is a good estimate for the sum which concerns all primes not exceeding $x$: $$\sum\limits_{p\leq x}\frac{1}{p^s}$$$$0<s<1$$. Only this. Thanks in advance!
-1
votes
1answer
41 views

Big O Notation for a constant running time

I came across a question asking the following: Why is the O-notation for a constant running time always given as O(1)? I have been thinking about it but I can't make sense of it. Could anyone ...
2
votes
2answers
91 views

Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$

I want to prove the following that based on maximum rule of functions: $$\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$$ the base prove is for each 2 functions ...
0
votes
3answers
2k views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
0
votes
2answers
140 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
1
vote
1answer
121 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...