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

learn more… | top users | synonyms (1)

-1
votes
1answer
31 views

Finding the Time Complexity in Big theta notation [closed]

sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ...
2
votes
1answer
56 views

Does satisfy $f(n)=\frac{\sigma(n)}{n^2}$ the hypothesis of Halasz’s inequality?

Let $\sigma(n)=\sum_{d\mid n}d$ the sum of divisor function. I would like to know if I can write an example of some of the following Theorem 1 or Theorem 2 from $$f(n)=\frac{\sigma(n)}{n^2}$$ in Tao, ...
0
votes
2answers
54 views

Is there an way to calculate the value of O(n) [closed]

Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated?
1
vote
1answer
64 views

Converse of the Watson's lemma

Watson's lemma basically says $$ f(t) \sim t^{\alpha} \,\,\,(\text{for small } t) \implies \int_0^{\infty} f(t) e^{-st} dt \sim \frac{\Gamma(\alpha + 1)}{s^{\alpha + 1}} \,\,\,(\text{for large } s). $...
2
votes
1answer
44 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
1
vote
0answers
33 views

Upper bounding a sum of products

Let $a_k$ be an integer valued sequence, $a_k \in \mathbb{N}^+$ and let $b_k = \#\{i: a_i=1,\; i \leq k\}$ and assume that $b_k=o(k)$ (little o notation). How to prove that there exists a constant $...
0
votes
0answers
23 views

Asymptotic behavior of inverse laplace transform [duplicate]

My question may be quite rough. Let $F(\lambda)$ be the Laplace transform of some function $f(t)$, $$ F(\lambda)= \int_0^\infty e^{-\lambda t}f(t) dt. $$ If I have knowledge about $F(\lambda)=O(\...
2
votes
1answer
37 views

Asymptotic lower bound of this function

Suppose that $n$ is an even number. Let $$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$ Can we find some function $g(n)$ (e.g. $\log(n)$ or $n^\alpha$) such that $f(n)=\Omega(g(n))$? ...
-2
votes
2answers
54 views

Using the definition of $f$ is $O(g)$ proof: [closed]

I'm studying for my discrete math class and I don't understand how to prove big O notation. I understand that $f$ is $O(g)$ of another if $f(x) \le c g(x)$ holds. How would I go about proving $\sin ...
2
votes
1answer
72 views

Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
1
vote
2answers
73 views

Help with a limit using big O?

$\lim_{x\to 0} \frac{4sin^{2}(\frac{x}{2})-x^{2}cos(\frac{x}{2})}{4x^{2}sin^{2}(\frac{x}{2})}$ is equal to $\frac{1}{24}$ apparently but I can't work it out. My attempt: $\lim_{x\to 0} \frac{4(\frac{...
0
votes
1answer
22 views

asymptotic notations : if $0<a<b$ then $n^b=\Omega(n^a)$

If $0<a<b$ then $n^b=\Omega(n^a)$. I have learned about this quiet recently and have come across this equation. I am having difficulty proving this. Any help would be appreciated.
0
votes
0answers
24 views

Doubts and computations about Dirichlet series and aliquot sequences I

Perhaps the more easier statement that one can deduce for aliquot sequences (which is the Wikipedia's Page) is the following Lemma. For an integer $n\geq 1$, let $s^0(n)\equiv n$, $s(n)\equiv s^1(...
6
votes
1answer
2k views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...
0
votes
0answers
29 views

Combinatorics of classifying objects.

Given a multiset of $n$ primes (with product of multiset less than $2^{n\log n}$) how many ways can we assemble them into $k$ composite number of equal size? I am looking for asymptotics.
8
votes
1answer
238 views

How to solve the non-linear differential equation $y''=x-y^2$?

$y''(x)=x-y^2(x)$ I'm particularly interested in solutions when $x>0$. I've performed asymptotic analysis and reached the conclusion that solutions must behave as $\pm\sqrt{x}$ when $x\rightarrow ...
4
votes
4answers
107 views

Decreasing function that behaves like $1-x^2$ for small $x$ and like $e^{-x}$ for large $x$

I am trying to find a function with a domain $D = \mathbb{R}_+$, that is behaving like $1-x^2$ for small $x$ and like $e^{-x}$ for large $x$. Edit: And is monotonically decreasing. I thought about ...
0
votes
0answers
24 views

Some doubts related to Lovasz Local Lemma.

I have 2 question regarding Lovasz Local Lemma. In the book Probability and Computing: Randomized Algorithms and Probabilistic Analysis , it is shown that $Pr(\cap_{i=1}^n \overline{E_i}) \ge (1-...
1
vote
2answers
33 views

Correct order of the growth function [closed]

$5 \log( \log n) $ $n (\log n)^2$ $\sqrt{n} \log n$ $n^{\frac{4}{3}}$ $n \log (\log n)$ $7 \sqrt{n}$ What is the ascending order of the growth function? Please give the explanation as well.
1
vote
3answers
39 views

Asymptotic expansion of ratio function

I want to expand the following function: $$ f(x)=\frac{1}{(1-e^{-x})} $$ $f(x)$ can be rewritten as $$ f(x) \sim \frac{1}{x-x^2/2 + x^3/2/3} $$ But I want to express big-oh notation such that $$ f(...
0
votes
1answer
34 views

Which one grows faster?

Is the following statement true or false? $(\log n)^{10} = O(n^{0.10})$ When trying to solve this, I thought it was false, but according to my teacher's answers, it's true. I would like to know if ...
0
votes
0answers
30 views

Multiscale asymptotic expansion of differential equation with a constant

My question is: How to apply a two-time asymptotic analysis to the equation: $\frac{\partial v}{\partial t} + v\frac{\partial v}{\partial x} = \beta+\,\,\frac{d I}{d x}$ $\,\,\,\,\,\,\,\,\,\,...
2
votes
2answers
64 views

asymptotic behaviour of the integral without Laplace’s method

I don't know asymptotic behaviour of the integral $$\int_{0}^{\infty}\frac{du}{\sqrt{4\pi u^{3}}}\left(1-\frac{e^{-\Omega u}}{\sqrt{\frac{1-\exp\left(-2u\right)}{2u}}}\right),$$ when I read a physics ...
0
votes
0answers
20 views

Landau notation related question

Hi :) Just a quick question here. When you put $cos(x)$ into wolframalpha, it says that the taylor series expansion about $x=0$ is $1 - \frac{x^2}{2} + \frac{x^4}{24} + O(x^6)$. My question is, how ...
2
votes
1answer
46 views

Is $x^x$ in the same asymptotic growth class as an exponential function?

I see that for any natural number $a$, $\lim_{x\to\infty} \tfrac{x^x}{a^x}$ approaches $\infty$, so the limit does not exist. So is this function have a different big-O than $O(a^x)$, for example? So ...
0
votes
0answers
14 views

Asymptotic Solution to ODE

Suppose $a(x)\sim b(x)$ when $x\rightarrow + \infty$. When is the solution of $F(y', y, x, a(x))$ asymptotically equivalent to the solution of $F(y', y, x, b(x))$? The method of dominant balance ...
4
votes
1answer
104 views

Can I integrate an asymptotic expression?

Suppose that $y(x; \epsilon)$ is a real-valued function of $x \in [a,b] \subset\mathbb{R}$ depending on a real parameter $\epsilon$, and that \begin{align} \int_a^b dx \ y(x; \epsilon) =& 1 &&...
0
votes
0answers
29 views

Incomplete Gamma Asymptotics

my question is simple : if $a_n$ and $z_n$ are both real positive sequences tending to $+\infty$, what is the asymptotic ($n \to +\infty$) behaviour of $\Gamma(a_n,z_n)$ when 1) $a_n \neq z_n$ and $\...
2
votes
0answers
52 views

A Simple Stochastic Integral Asymptotics

Let $B(t)$ be the standard Brownian motion, $\mu(t,x)$ and $\sigma(t,x)$ are continuous functions, and $$dr(t) = \mu(t,r(t))dt+\sigma(t,r(t))dB(t).$$ $(\mu,\sigma)$ obeys the linear growth condition $...
1
vote
1answer
14 views

How is it true that for large $t$, $(1+O(1/t))e^{-2\ln t O(1/t)}=1+O(\ln t/t)$?

The title pretty much says it all. At some point in large time analysis, the following claim popped out but I don't see how it is true: For sufficiently large $t>0$, $$ \frac{2\ln t}{t}(1+O(1/t))e^...
0
votes
1answer
35 views

What is an accurate approximation and asymptotic for this function?

$$f(n)=\Bigg(1-\Big(1-\frac{1}{2^{n/2}}\Big)^n\Bigg)^{n^7}$$ I am interested in large $n$. The number $7$ can be replaced by any fixed integer. I have $$f(n)\rightarrow\Bigg(1-e^{-n2^{-n/2}}\Bigg)^{...
8
votes
5answers
373 views

Asymptotic behavior of $\sum\limits_{k=1}^n \frac{2^k}{k}$

I'm looking for an asymptotic equivalent of $$\sum_{0 < k \le n} \frac{2^k}{k}$$ as $n \to \infty$. A plausible candidate seems to be $\frac{2^{n+1}}{n+1}$ (WolframAlpha plot, and the intuitive ...
0
votes
2answers
40 views

Asymptotic evaluation of a quantity

Can we say that the following quantity (a recursion of logarithms): $W_{-1}(x)=\ln \cfrac{-x}{-\ln \cfrac{-x}{-\ln \cfrac{-x}{...}}}$ is $\Theta(\ln x)$? i.e., asimptotically upper and lower bounded?...
0
votes
0answers
9 views

Reference Books on Asymptotic theory of Statistics and Probability

Can anyone suggest me some good reference books on Asymptotic Theory of Statistics and Probability for students pursuing a post-graduate degree in Statistics ? It would be very much helpful if the ...
5
votes
1answer
56 views

Asymptotic expansion of $(1+\epsilon)^{s/\epsilon}$

I have taken the logarithm of this expression and computed the Taylor expansion of the $\log(1+\epsilon)$ term but by doing this we're required to calculate powers of this series when using the ...
2
votes
2answers
45 views

Estimate for a prime product.

Is there a bound for $$\prod_{i=1}^{m}\Big(1-\frac{1}{p_i}\Big)$$ where $p_i$ is $i$th prime? What if $m=O(\log n)$?
4
votes
1answer
43 views

Density of a set of numbers.

Firstly, I introduce a notation. $\Bbb{N}$ denotes the set of natural numbers, $0$ included. For $E \subseteq \Bbb{N}$ and $n \in \Bbb{N}$, I denote by $$\pi_E(n) = |E \cap \{ 1, \dots , n\}|$$ and $$...
0
votes
1answer
18 views

Finding the upper tight bound of a mathematical function. (Big O)

I am trying to understand Big-$O$ notation through a book I have and it is covering Big-$O$ by using functions although I am a bit confused. The book says that $O(g(n))$ where $ g(n)$ is the upper ...
5
votes
5answers
45 views

For some arbitrarily fast growing function $f$ and a strictly sublinear function $g$, can $g \circ \cdots \circ g \circ f$ always grow polynomially?

Given two functions $f, g: \mathbb{R}_{≥ 0} \to \mathbb{R}_{≥ 0}$ that are monotonically growing, with $g(x) \in o(x)$ (i.e. $g$ grows strictly sublinear), does there always exist an $m \in \mathbb{N}$...
1
vote
2answers
30 views

As $x \to 0$ this approaches zero since the zero of $e^{\frac{-1}{x^2}}$ beats out the pole of $\frac{1}{Q_k(x)}$?

In the Robert Strichartz's book "A Guide to Distribution Theory and Fourier Transforms" at the page $4$, we have an interesting exercise : $$ \psi(x) = \begin{cases} e^{\frac{-1}{x^2}} &...
1
vote
2answers
15 views

How to calculate duration of event at different speeds

Specifically I want to figure out the formula which will tell me: how long will it take to watch this video (normal length $L$) at speed $x$. I think this will be asymptotic, no matter how fast you ...
-1
votes
2answers
54 views

Asymptotics of $\sum_{n}e^{-n^{2}}$.

Define the function $S(N)$ as $$S(N)=\sum_{n=0}^{N}e^{-n^{2}}$$ I am interested in the asymptotic behavior of $S(N)$ for large $N$. It is clear by the ratio test that $\lim_{N\rightarrow\infty}S(N)$ ...
1
vote
0answers
37 views

Non-trivial inverse Laplace transform

I'm trying to compute the inverse Laplace transform of $f(s) = s^c/(N + s^{ir} )$ where $c,N \in \mathbb{C}$ and $r \in \mathbb{R}^+$ using the Bromwich integral $$ F(t) = \frac{1}{2 \pi i} \int_{- ...
0
votes
1answer
22 views

Find the inner solution

I need to show that the leading order inner solution is given by the below. Thus far, I have rescaled and showed the boundary layer is of order $\epsilon^{\frac{3}{4}}$. Hence at leading order I then ...
1
vote
1answer
97 views

Show $R(x)=o(x^3)$

I got $$R(x)=4! \, x^4 \int _0^{\infty} \frac{1}{(1+xt)^{5}}e^{-t} \, \, dt$$ is this correct? I have no idea what to do for the last part of ii
1
vote
0answers
33 views

Order Size estimation of converging sum used for approximation of logarithm

I know it can be shown that $\log n=\sum_{i=1}^\infty \frac{(n-1)^i}{in^i}$ for $\forall n\in\Re$ where $n\ge1$ For given natural m, I tried to find the order size of k = f(m,n) in order for the ...
0
votes
1answer
14 views

Asymptotic notation basics

Say that we have the function $$ f(n)=kn, \, k>0 $$ does that imply the following? $$f(n) \in O(n), \, f(n) \in \Theta(n) \text{ and } f(n) \in \Omega(n)$$ I'm fairly new to these notations and am ...
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
0
votes
2answers
33 views

Find the asymptotics of $n(\frac{n-1}{n})^n$ [closed]

Find the asymptotics of $n(\frac{n-1}{n})^n$. I know $f(x)$~ $g(x) $ if $lim\frac{f(x)}{g(x)}=1$ but I am unsure as to how I found $g(x)$ I found a solution $\frac{2n-1}{2e}$ but I am unsure where ...
0
votes
0answers
20 views

Justify Why Boundary Layer Exists at x=0

With part a of this question (I asked about latter parts before), does it suffice to find the outer solution and show that since both boundary conditions cannot be met, then there exists a boundary ...