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

Long division for multipolynomial expression, little o notation

I have this expression: $$\mathrm{Exp}=\frac{1}{1-a}+\frac{d^3(-12a^4)+d^2(4a^4-16a^3)+d(4a^3-6a^2-a)}{d^3(-12a^4+12a^3)+d^2(4a^4-20a^3+16a^2)+d(4a^3-11a+7a)+(1-2a+a^2)}$$ Is there any way I can ...
0
votes
1answer
16 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
0answers
7 views

(Empirical likelihood method) Find the order of a parameter given a set of constraints

Firstly we assume that $X_1,...X_n$ are order statistics($X_i\leq X_{i+1}$) from an i.i.d sample of random variables and let $r$ be integer and $r\geq1$. Start with the equation (1) \begin{equation} ...
-1
votes
1answer
17 views

If $nE\|X_n-Y_n\|^2=o(1)$, why $\sqrt{n}(X_n-Y_n)=o_p(1)$ [on hold]

How to show that if we have $nE\|X_n-Y_n\|^2=o(1)$, then $\sqrt{n}(X_n-Y_n)=o_p(1)$? Here $X_n,Y_n$ are two random elements.
2
votes
1answer
26 views

Evaluating the leading term of asymptotics

I am struggling with this problem where we're asked to use Laplace's method: Find the leading term of the asymptotics of the following intergral for $\lambda\to\infty$: $$\int_0^{\infty} ...
2
votes
0answers
14 views

Asymptotics of Laplace transform at minus infinity

I am interested in relating the asymptotic behavior of a function $f(t)$ for large values of $t$ with the asymptotic behavior of its Laplace transform $\hat{f}(s)$ for small values of $s$. In practice ...
-1
votes
1answer
28 views

Multiplying logarithms of different bases [on hold]

How do you multiply the following logs... $$\log_5(n) * \log_2(n)$$
8
votes
1answer
183 views

Complexity $O(n^3)$ vs $O((\log n)^4))$

I would like to prove that $O(n^3)$ is bigger than $O((\log n)^4)$. I thought that I can divide both powers with 4 so it is $$O\left(n^{\frac{3}{4}}\right)$$ vs $$O(\log n)$$ but then I don't know ...
1
vote
0answers
18 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
1
vote
1answer
80 views

Integrate 1/ln(ln(x)) asymptotically

I was looking for the asymptotic behaviour of the anti-derivative of $\frac{1}{\ln \ln x}$, in terms of the big-O notation. Wikipedia's list does not have this integral, and Wolfram Alpha says "no ...
2
votes
2answers
52 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
1answer
38 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
2
votes
0answers
35 views

Asymptotic expression of $\int_{- D}^{D} \frac{\text{tanh}(\xi)}{\xi -\omega}\mathrm{d}\xi$

How to derive the following asymptotic expression ($|\omega| \ll D $)? $${\cal{P}}\int_{- D}^{D} \frac{\text{tanh}(\xi)}{\xi -\omega}\mathrm{d}\xi \approx ...
2
votes
0answers
32 views

The series may converge, but what about the series / n?

Let $a_i$ be a positive sequence such that $a_i \to 0$. I know that the series $\sum_{i=1}^\infty a_i$ may be divergent. But what about the series divided by $n$; does the following go to 0? ...
1
vote
1answer
26 views

About the equivalence of two asymptotic probabilistic statements

Let $g(n)$ be some monotone increasing function of naturals, and let $X_n$ be a sequence of positive random variables. Consider the following two claims: Claim 1. $\exists f=o(g(n)),\ ...
5
votes
0answers
43 views

Show that $1^k+2^k+…+n^k$ is $O (n^{k+1})$.

Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$. So according to the definition of big-$O$ notation we have: $$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$ whenever $n>1$ Is ...
0
votes
3answers
64 views

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$ The definition says: We say that $f(x)$ is $O (g(x))$ if there are constants $C$ and $k$ such that $$\mid f(x) \mid \leq C \mid g(x) \mid$$ whenever $x > ...
0
votes
0answers
24 views

uniform limits and asymptotic equivalence

I am told that $\frac{f(\lambda r)}{f(r)}$ tends to 1 uniformly in $\lambda$. I also know that $x(t)$ is asymptotically equivalent to $ct$, so $x(t)\sim ct$. How can I show that $\frac{f(x(\lambda ...
0
votes
0answers
28 views

To determine asymptotic value of funtion for large N

To show that the function follows normal Gaussian for large value of N (s.t. m is much less than N ) with mean at 'm'. $f(m,N)=\sum_{a=1}^{\lfloor N/2 \rfloor} \binom{N}{S} * ...
1
vote
0answers
30 views

Asymptotic Formula for Sum

I am trying to find an asymptotic formula for the sum of the following: $\sum _{x=1}^{\infty } x \left(\left(1-\frac{\Gamma (x,\lambda )}{\Gamma (x)}\right)^n-\left(1-\frac{\Gamma (x+1,\lambda ...
0
votes
1answer
14 views

natural logarithmic to asymptotic order

Say we have an equation $\lambda_{\epsilon}(s)=-\frac{1}{\pi s^2}\ln(1-\epsilon)$ $\forall s\in (0,(M \mathcal{k})^{-\frac{1}{\alpha}})$ where $s$ can be obtained by $s=(M ...
2
votes
1answer
34 views

Large and small time PDE solution

I have the following solution for a PDE $$ u(x,t)=(2x+4t-10)+2e^{\frac{-1}{2}t}+\sum_{n=1}^{\infty} \frac{(-1)^n cos(\frac{n\pi}{2}x)e^{\frac{-1}{4}n^2\pi^2t}}{n^3\pi^3(n^2\pi^2-2)} $$ I want to ...
0
votes
2answers
27 views

Why can any values of C and N be chosen for the proof of Big-Oh?

In my CS course, they have taught us that, when proving Big-Oh, you can choose any positive integers to be C and k, following the definition. Based on that, they have taught us two different ways of ...
1
vote
1answer
24 views

Asymptotic behaviour of sequences

Could anyone explain in details how these approximations as $n \to \infty$ are found? ($a$ is a positive real number) ${x_n} = \frac{1}{n}\left( {\frac{a}{3} - \frac{3}{2}} \right) + O\left( ...
3
votes
1answer
42 views

Help understanding the complexity of my algorithm (summation)

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are ...
1
vote
1answer
13 views

Asymptotic stopping time for a ball-drawing problem

Take two different boxes, one with $N$ red balls and one with $N$ blue balls. Remove balls one at a time from either box with equal probability. When only one color is left, the (expected value of ...
0
votes
0answers
13 views

Limit of an indeterminated form?

I want to find: $$\lim_{t\to\infty}X_{t}$$ where: $$X_{t} = \frac{A_{t}^{a}}{B_{t}}$$ I know that: $$\lim_{t\to\infty}A_{t}=0$$ and $$\lim_{t\to\infty}B_{t}=0$$ Can I say with certainty that: ...
1
vote
1answer
28 views

Approximation of a generlized hypergeometric function for large parameters

I am looking for an approximation of a generalized hypergeometric function of the type $\, _0F_4$. I've stumbled upon the following approximation : assuming that none of a1,a2,…,ap is a nonpositive ...
0
votes
0answers
16 views

Doubt on asymptotics of continous functions (little-o notation and taylor expansion).

Suppose I have $e^{(\frac{1}{n}b + o(\frac{1}{n}))}$ then $\lim_{n \rightarrow \infty} = e^0 = 1$ so $$e^{(\frac{1}{n}b + o(\frac{1}{n}))} = o(1) +1$$ But if I take the Taylor expansion of ...
0
votes
0answers
16 views

Solution for asymptotic parametric equation

Say I have the following equation: \begin{equation} f(x) = A(t)^{c}g(x)h(x) \end{equation} where $\lim_{t\rightarrow \infty} A(t) = \infty$. Very importantly, $x \in [0,1]$. I want to find the ...
-2
votes
1answer
26 views

Approximation for the Summation of Sequence of Powers of Sines Functions. [closed]

Let $z_1,z_2,...,z_m$ be real numbers such that $0<z_1,z_2,\ldots,z_m<\pi/2$, $z_1>z_2>...>z_m$ and $n$ an integer such that $n>0$. Prove that: ...
2
votes
0answers
39 views

Question related to the ballistic motion

A point mass will move in the gravitational field of the Earth according to the equation $$\ddot R =-\frac{GM_eR}{|R|^3},$$ where $R$ is the position vector of the point mass measured from the ...
2
votes
0answers
39 views

Asymptotic expansion of root of $\epsilon x \tan(x)=1$

Indicate a range of roots of $\epsilon x \tan(x)=1$ for which it is impossible to get an approximation using expansions. Since $\epsilon$ is small, I think for the equation to hold, we need ...
1
vote
2answers
47 views

A further question on asymptotic expansions of all real roots of xtan(x)=ϵ

I have asked a related question here How to find asymptotic expansions of all real roots of $x \tan(x)=\epsilon?$, however, when I discussed with my adviser today, he argued the solution is flawed. ...
0
votes
0answers
9 views

The size of the vertex hull of a lattice

Let $L$ be a lattice defined by $d$ vectors in $\mathbb{R}^d$. The Vertex Hull of a node $a$ at radius $r$ (denoted $VH(a, r)$) is defined to be the set of vertices that define the convex hull of $L ...
0
votes
4answers
79 views

Does $\lim \frac{a_n}{e^{\delta n}}=0$ for every positive $\delta$ imply that $\lim \frac{a_n}{\sum\limits_{k=1}^n a_k} =0$

Let's say we have an increasing sequence $a_n$ such that $\underset{n\rightarrow\infty}{\lim} a_n=\infty$. Now it's fairly clear to me, though I haven't proven this yet, that: ...
2
votes
1answer
20 views

Multiplying two matrices using Strassen vs squaring identical matrices

I have an assignment question such as follows: when using the Strassen algorithm we have 7 subproblems usually, and I suppose this applies to any two $n*n$ matrices and the run time is ...
3
votes
1answer
51 views

Asymptotic expansion of integral $F_m=2 \int_m^ \infty p(x)dx$.

$$p(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$$ is the probability density function of the standard normal random variable. m-sigma quality control means that the probability of failure is less ...
0
votes
1answer
18 views

Difference between a convergent series and an asymptotic series?

Can someone let me know the difference between a convergent series and an asymptotic series with an example? Can both the series be the same at some situations? In what situations an asymptotic series ...
2
votes
2answers
76 views

How to find asymptotic expansions of all real roots of $x \tan(x)/\epsilon=1?$

Find expansions of all the real roots of $$x\tan(x)=\epsilon?$$ (You have to consider the first root separately) It is really bothering me. If I assume $x=x_0+x_1\epsilon +x_2\epsilon^2$ and do ...
6
votes
0answers
117 views

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
0
votes
0answers
114 views

CDF of sum of 3 independent discrete uniform random variables on {1,2,…,n}

What is an approximate closed formula for this probability, with a derivation: p(k,n) is the probability, that among $n$ PC discs and $k$ errors in sum on them, there will be at least $1$ disc ...
0
votes
0answers
11 views

Asymptotic complexities of a conditional function

Let the function $f(n)$ be defined by $$f(n) = \dfrac{n^2}{7}$$, for n even and $$f(n) = 452n$$, for n odd I'm being asked to determine which statements are true and to show validation for those ...
2
votes
0answers
25 views

Asymptotic analysis of coefficients of ordinary generating functions with radius of convergence $1$ seems to always predict polynomial growth rate

Wikipedia gives the following formula for obtaining asymptotic information about the coefficients of an ordinary generating function from information about the generating function itself: if the ...
-1
votes
0answers
47 views

What is the slow manifolds? and how to calculate?

I'm a newbie in slow manifolds and dynamical system. I cannot understand the concept of slow manifolds and how to calculate that. Please explain the concept of slow manifolds intuitively and ...
0
votes
0answers
14 views

behavior of function

Im looking at the asymptotic behavior of the function $f(x)=x-c(\lceil \frac{x}{c} \rceil)$ as $x \rightarrow \infty$ for some constant $c>0$. I believe this function is bounded above by $0$ ...
1
vote
2answers
53 views

Notation issue - Asymptotic behaviour: is $\sim$ too restrictive?

As a student I am completely unable to understand unambiguously what is meant by a notation such as $$f \sim g $$ when in Physics the behaviour of two functions at infinity is evaluated. I found a ...
0
votes
1answer
25 views

Understanding Asymptotic Notation of a constant

How can I prove that if $f(n) = O(1)$ leads to $f(n) = \Omega(1)$ as well? I need a Formal definition of the meaning that a function $f(n) = O(1)$
0
votes
1answer
50 views

Prove that$ f(x)=\ln(x)$, where $ x>0$ is of exponential order.

Prove that$ f(x)=\ln(x)$, where $ x>0$ is of exponential order. I know that if there exists a constant a and positive constants $t_0$ and $M$ such that $|f(t)| \leq M e^{at}$ at for all $t > ...
-1
votes
1answer
26 views

The asymptote of $y=\mathrm{sinc}(t)$ as time increases

Is there any known approximate formula that maps decay percentage of $\mathrm{sinc}(t)$ with decaying time? Or in other words, is there a known asymptote of $y=\mathrm{sinc}(t)$ as time increases?