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
0answers
43 views

How does one begin to find an asymptotic function of an infinite power series?

Say we have the infinite series $$\sum_{n=0}^\infty a_nx^n.$$ We want to attempt to find an asymptotic function/relation to the above series. How does one begin? I have never dealt with this area of ...
0
votes
1answer
48 views

If f(n)∈Ω(n) how do I prove or disprove f(n)∈O(n)

If f(n)∈Ω(n) how do I prove f(n)∈O(n) I feel it is true, but not sure how to show it the way I see it c1*n =< f(n) =< c2*n holds, but so confused on how to show it
1
vote
1answer
44 views

Cancellation of Asymptotics

Suppose $f,g,h$ are real functions defined on a neighborhood of $\infty$ such that $f\circ g=\Theta(f\circ h)$. Under what conditions on $f$ does it follow that $g=\Theta(h)$? For instance, it ...
14
votes
1answer
217 views

If $\lambda_n \sim \mu_n$, is it true that $\sum \exp(-\lambda_n x) \sim \sum \exp(-\mu_n x)$ as $x \to 0$?

If $\lambda_n,\mu_n \in \mathbb{R}$, $\lambda_n \sim \mu_n$ as $n \to +\infty$, and $\mu_n \to +\infty$ as $n \to +\infty$, is it true that $$ \sum_{n=1}^{\infty} \exp(-\lambda_n x) \sim ...
0
votes
1answer
64 views

Big O: Prove that for all $x \leqslant y$, $n^x \in \mathcal O(n^y)$

For all real numbers, if $x \leqslant y, n^x \in \mathcal O(n^y)$. This is a homework question, so I'm just looking for a little guidance with this question, and not the answer. I understand how to ...
2
votes
0answers
288 views

First disagreement in PROUHET THUE MORSE exponentially big?

Let two sequences of integers be $a_1, \cdots, a_n$ and $b_1, \cdots, b_n$ such that with $a_i \in \{1, \cdots n\}$ and $b_i \in \{1, \cdots, n\}$. Let $k$ be the min integer such that $\sum_{i=1}^n ...
2
votes
2answers
142 views

Find the order of magnitude of the equation solution

Find the order of magnitude of the following equation solution: $$ x(\ln x)^{2001}=n $$
2
votes
1answer
49 views

How to evaluate square of logarithms to solve s(n) = O(a(n))?

I've never used log before, nor worked with big-O notation, so I'm completely useless at this stuff. Any, any, any help or direction you can give would be helpful as the professor hasn't covered this ...
0
votes
1answer
95 views

compare n^log log n with c^n and n^k

What is the relation in terms of asymptotic analysis, between n^log log n and $c^n$,$n^k$ ? how can find relation between such functions?
2
votes
2answers
29 views

Prove ∀a∈R, ∀b∈R ,[(a <= b)⇒(n^a ∈O(n^b))]

We have just started learning the Big O notation and have been asked to prove this statement: $$ \forall a,b \in \mathbb{R}, a \leq b \implies n^a \in O(n^b) $$ I am really confused how to ...
0
votes
1answer
50 views

Find beginning of the asymptotic expansion of the sum

Find beginning of the asymptotic expansion of the sum: $$ (n!)^{-1}\sum^{n}_{k=1}k! $$ against the function $n^{-i}$, for $i\geq0$ to the nearest $\mathcal{O}(n^{-5})$.
1
vote
0answers
103 views

Asymptotic estimate of coprime pairs of integers $\leq n$.

Let $M_{n} = \{(x,y) \in [n] \times [n]: xy \leq n^{2} \text{ and } gcd(x,y) = 1\}$, where $[n] = \{1, 2, \dots , n\}$. In other words, let $M_{n}$ be the set of pairs of coprime integers both $\leq ...
1
vote
2answers
75 views

Can we get the formula for $\prod\limits_{k=0}^n{(1+2^k)^2}$ in terms of $n$?

Can we get the formula for $\prod\limits_{k=0}^n{(1+2^k)^2}$ in terms of $n$?
2
votes
2answers
53 views

interpreting limits

a short question: is this true that if: f(x) = $2^x$ g(x) = $100^\sqrt{x}$ $\lim\limits_{x \to \infty} \dfrac{f(x)}{g(x)}$ = $\infty$ then for x sufficiently large f(x) is always greater than ...
3
votes
1answer
109 views

Finding an asymptotic expansion for a transcedental equation

I am new around here and was hoping you will be able to help me with the following. I have the equation: $x^3 - 3x^2 +(3-\epsilon ) x + \epsilon = sin(\frac{\pi}{2} x +\frac{\pi \epsilon}{2} ) $ and ...
5
votes
0answers
331 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
20
votes
5answers
751 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.
0
votes
1answer
48 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 ...
3
votes
2answers
524 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
92 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 ...
2
votes
1answer
68 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
46 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
384 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
48 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
101 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 ...
1
vote
1answer
52 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; ...
2
votes
1answer
328 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 ...
6
votes
1answer
61 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 ...
1
vote
1answer
173 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
95 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
559 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 ...
2
votes
1answer
77 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 ...
1
vote
2answers
71 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
135 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 ...
5
votes
1answer
128 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
48 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
1answer
455 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
59 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
251 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 ...
3
votes
1answer
143 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
315 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 ...
9
votes
2answers
278 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 ...
1
vote
2answers
810 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 ...
2
votes
1answer
92 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
112 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
81 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
365 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
1answer
84 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
113 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$ ...
3
votes
1answer
127 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 ...