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

I am looking a comparison of this computation and Riemann's approach for $lcm(1,2\ldots,x)$

Looking a comparison with a reasoning due to Riemann, I ask to me about the behaviour as $x\to\infty$ of the following arithmetical function $$ \left( \prod_{n\leq x}n^{-\mu(n)}\right)\cdot \left( \...
1
vote
1answer
31 views

Asymptotic notation: What does $o(\epsilon_\text{mach})$ mean?

I'm having serious problems to understand what people mean when they write $o(\epsilon_\text{mach})$, where $\epsilon_\text{mach}$ stands for the machine epsilon. I'm seeing this in backward analysis ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
1answer
44 views

Finding family of curve for given asymptotes

I need to find possible curves, with asymptotes given as $x=0 (x \to -\infty)$ and $y=mx \hspace{0.5cm} m>0$. it is easy to find curves for individual lines, $y= \exp(-\lambda_1 x) + mx$ for $y=mx$ ...
0
votes
2answers
38 views

Big O for a $\cos$ series

I have to show that $ \sum_1^N \cos(nx) = O(\frac 1{|x|}), [-\pi, \pi] $, x different from 0. I really don't know how to show that. I obviously know that $\cos(nx)$ is bounded by $1$, I know what ...
1
vote
0answers
35 views

Products of $k^{\mu(k)}$, where $\mu(n)$ is Möbius function, and the Prime Number Theorem

We can write $$e^{-\Lambda(n)}=\prod_{d\mid n}d^{\mu(d)},$$ where $\mu(n)$ is the Möbius function and thus $\Lambda(n)$ is von Mangoldt's function. Then taking the product from $1$ to $N$ we've for ...
0
votes
1answer
18 views

Simple Sigmoid function that levels off at specific points

I need to construct a simple Sigmoid function that levels off at specific values of x, as in this curve: What is the most simple Sigmoid function that I can use ...
-2
votes
5answers
100 views

Hello. I need to show that $\sqrt n$ grows faster than $(\log n)^{100}$ [closed]

Is there an easy way to show that $$\lim_{n\to \infty}\frac {(\log n)^{100}}{\sqrt n}=0 $$
5
votes
2answers
71 views

How is it posible that $f + g \in O(f)$?

I am confused how to do this question. Intuitively it doesn't even make sense how a function $f$ plus another function is in $O(f)$. How can I approach this question: $$ n\log(n^7)+n^{\frac{7}{2}} \...
0
votes
1answer
46 views

Determine numerical infinity for Schrodinger equation $−\psi''(z) − (iz)^ N \psi(z) = E\psi(z)$

Consider the following one dimensional Schrodinger equation within the complex plane of $z$ $$ −ψ''(z) − (iz)^ N ψ(z) = Eψ(z). $$ where $N$ can be any real number, the boundary condition is $ψ(z) → 0$ ...
0
votes
1answer
13 views

Which one is asymptotically larger?

The question is to find out which among $n^\sqrt{n}$ or $n^(log_2 n)$ is asymptotically larger? Now as a solution I read somewhere that if we take log on both sides and then compute which one is ...
3
votes
2answers
89 views

Prove that the value of the constant $C$ must be $1$

After proving the prime number theorem in class, our professor directs us to a remark by Lagrange that for large values of $x$, $\pi(x)$ is approximately equal to $$ \frac{x}{\log x - B}. $$ (This is ...
0
votes
0answers
17 views

Asymptotic growth of $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$

Can you give a solution or a hint for finding asymptotic bound for following recurrence relation: $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$ I know from the source of the problem that it is $\...
1
vote
2answers
46 views

If for some $n\in\mathbb{N}$, $\lim\limits_{x\to\infty}\frac{f(x)}{x^n}$ exists, then $f$ is rational

I don't know if this statement is true. Let $F$ be a function and suppose $n>0$, $n\in\mathbb{N}$ is the greatest such that there exists $L\mathbf{\neq 0}$ such that $\lim\limits_{x\to\infty}\frac{...
2
votes
0answers
35 views

Asymptotic distribution of zero-drift Geometric Brownian Motion as $t \to \infty$

If we fix the drift at $\mu = 0$, then my geometric brownian motion will have stationary mean, but it seems that the variance will grow without bound. What does the limiting distribution look like for ...
0
votes
0answers
8 views

Rate of expected value of $\mathcal{O}_p$

This is certainly very basic but what is the rate of the expected value of a random variable that is bounded in probability. For example, let $X_n = \mathcal{O}_p (a_n)$ is it true that $\mathbb{E} [...
0
votes
1answer
63 views

Prove that $n! = O(n^n)$

I thought $n^n$ was greater than $n!$. How would I go about proving this? I have this so far: Assume that $P$($n$) is true $n!$ = O($n^n$) Assume that $P$($n+1$) is also true $(n+1)! ...
0
votes
1answer
14 views

The Big O Notation and the Thetha Notation

I was instructed to find whether $$x*⌈x⌉*⌊x⌋$$ is$$ O(x^3) $$ or $$Big Thetha(x^3)$$ I tried to do a solution by cases, and i got : if x is not an integer, $$x=b+є$$ $$⌈x⌉=b+1$$ $$⌊x⌋=b$$ Then $$x*⌈x⌉*...
3
votes
1answer
41 views

Which singular perturbation method should be used for this system?

Consider the system $$ \varepsilon \dfrac{dx}{dt} = -(x^3 - ax + b)$$ $$ \dfrac{db}{dt} = x - x_a$$ where $\varepsilon \ll 1$. Applying regular perturbation methods isn't suitable because when $\...
0
votes
0answers
22 views

Linear combination of asymptotic series

I need to compute an expression of the form \begin{equation}J=\sum_{k=0}^N a_k F_k(z)\end{equation} where z is a large parameter, and a_k are easily computable (k and z-dependent) coefficients. I ...
8
votes
0answers
103 views

If $n={k^2 \choose k}$, then what is $k$?

Given that: $$n={k^2 \choose k}$$ what is $k$ as a function of $n$? So far, I have found the following approximation: $$ n \approx (k^2)^k = (k^k)^2 $$ $$ \sqrt{n} \approx k^k $$ If we take this ...
3
votes
2answers
359 views

Determining the number of levels in a binary tree via algorithm

I am trying to create a divide-and-conquer algorithm for computing the number of levels in a binary tree. In particular, the algorithm should return 0 and 1 for the empty and single-node trees, ...
-1
votes
1answer
24 views

Big O notaion O(n) and logaritms [closed]

Can someone explain me the subjects Big O notation and logarithms please? I can't understand those subjects For example if I have a question like this: recall that logan is the power to which you ...
1
vote
0answers
22 views

Finding asymptotycs of partition function

I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ...
3
votes
1answer
47 views

Verifying a step in the prime number theorem

This is an excerpt from Shapiro, "Introduction to the theory of numbers": Suppose that we have an estimate of the form $$|R(x)|\le \alpha x$$ valid for all sufficiently large $x$ (say $x\ge x_2$). ...
1
vote
1answer
59 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
0
votes
0answers
21 views

Asymptotic upper bound for recurrence relations

The question is to find asymptotic upper bound for recurrence: (1) $T(n)=(T(n/2))^2$ and (2) $T(n)=(T(\sqrt{n}))^2$ with $T(n) = \text{n for n} \leq 2$ I think I will be able to find the ...
0
votes
1answer
32 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: $T(n) = ...
0
votes
0answers
19 views

Big O notation question (conceptual)

In my class, we have defined that $$ f(x) \ll g(x) $$ on $A$ if there exist a strictly positive c such that $$ |f(x)| \le cg(x) $$ for every $x$ on $A$. I'm a bit confused. Say that $ f(x) = x$ ...
5
votes
1answer
173 views

Why does the asymptotic expansion of the real-valued Kummer function contain complex terms?

Working on a problem in spectral theory, I need to study the asymptotics of a confluent hypergeometric function (here $(a)_0=1$ and $(a)_s=a(a+1)\cdots(a+s-1)$ denote the Pochhammer symbol) $$ \...
0
votes
1answer
15 views

$\lim_{n\to\infty}\frac{f(n)}{h(n)}$ if $f\in o(g)$ and $g\in O(h)$

I would appreciate it if anybody could check my attempted solution to this question. I'm guessing since the question says 'values' rather than 'value' that I haven't finished the question. So if you ...
4
votes
1answer
61 views

The behaviour of $\sum k^a 2^k$.

Let $a$ be a real number, I want to find a simple equivalent (or if it is possible, an asymptotic expansion) of $$\sum_{k=1}^n k^a 2^k.$$ I believe that the sum is $\sim n^a 2^{n+1}$ (tried many ...
-1
votes
1answer
37 views

Prove little-o example [duplicate]

Let $f(x)=\log x$, and $g(x)=x^i$, where $0<i<1$. How can I correctly proof that $f(x)=o(g(x))$? Try 1: By the definition of little-o, a function is little-o of other function if $|f(x)|\leq C|...
2
votes
1answer
24 views

How to prove that $f(x)$ is $O(x^i)$ for a general polynomial

Let $f(x)=a_ix^i + a_{i-1}x^{i-1} + \ldots + a_0$ where $a_i>0$. How can I proof that this general polynomial with real coeficients is $O(x^i)$ using the Big-O notation theory. Try 1: I thought ...
0
votes
1answer
19 views

Proving equation using formal O(f(n)) - step by step?

I have huge problems showing whether example like this: is true or false using formal definition of Big O. How can I solve such problems step by step? I understand that formal definition of O(f(...
1
vote
1answer
35 views

Asymptotic behavior of Fourier transform and Hölder condition

I'm trying to solve this question. Following the hint, the Fourier inversion formula gives me : $$ \big| f(x+h) - f(x)\big| = \left| \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{i(x+h)\...
16
votes
1answer
456 views

An equivalent of $\int_0^1\left(\frac{1}{\log x}+\frac{1}{1-x}\right)^n\;dx$

Set $$ I_n :=\int_0^1\left(\frac{1}{\log x} + \frac{1}{1-x}\right)^n \:\mathrm{d}x \qquad n=1,2,3,.... $$ We have $$I_1 =\gamma, \quad I_2 =\log (2 \pi) - \frac 32, \quad I_3 = 6 \log A - \frac{...
1
vote
1answer
19 views

Proof of Property of little o

I am learning some asymptotic analysis and i'm trying to prove: If $\lim_{x\to c} f(x)< \infty$ then $o(fg)=o(g)$ (as $x \to c$). So far i have proved that $o(fg)\subset o(g)$, but i am stuck on ...
2
votes
1answer
71 views

How to prove $({\log_2 x})^{n+1} \le x^n$

I want to show that $({\log_2 x})^{n+1} \le x^n$ when $n \ge 1$ and $x \ge 1$. I know that ${\log_2 x}$ can be shown to be $\lt x$ with: $x \lt 2^x$ $\log_2 x \lt x$ and obviously adding the same ...
0
votes
1answer
16 views

Asymptotic behavior

I very much dislike the "Big Oh" notation. It just doesn't stick in my mind. Suppose $f$ is a continuous function and $f \in \text{O}( 1/|x|^{1+\epsilon})$ when $|x| \rightarrow \infty$ and for $0< ...
1
vote
1answer
20 views

Proof involving the Big-O notation

I am stuck on a proof question involving the big-O notation: Prove that if $f(x)$ is $O(x^3)$ then $f(x+x^2)$ is also $O(x^3)$. I am stuck because $f(x)$ can be any arbitrary polynomial. I started ...
0
votes
1answer
29 views

Graph with both slant and horizontal asymptotes

Is there such a graph? A graph that increases at a decreasing rate with the graph approaching a slant asymptote as x decreases to negative infinity while the graph approaching a horizontal asymptote ...
1
vote
2answers
32 views

asymptotic equivalence between harmonic numbers and logarithm

I have recently learned about asymptotical equivalence, defined as $$ a(n) \sim b(n) \Leftrightarrow \lim\limits_{n \to \infty} \frac{a(n)}{b(n)} = 1$$ Now I would need to prove that $H_n \sim \ln(n)...
2
votes
1answer
53 views

Inner solution of singular perturbation problem

Consider singular perturbation problem $$\epsilon \left[\frac{d}{dx}\left(h^3p\frac{dp}{dx}\right)\right]=\frac{d}{dx}(hp)$$ $$p(0)=p(1)=1$$ where $h(x)$ is a positive smooth function with $h(0)\ne h(...
1
vote
1answer
27 views

Showing $\psi(x)=\theta(x)+O(\sqrt x\log x)$ for Chebyshev's function $\psi$

In my textbook, there is the following theorem: For all $x>0$, we have $$\psi(x)=\sum_{\alpha=1}^\infty\theta(x^{1/\alpha})$$ and hence $$\psi(x)=\theta(x)+O(\sqrt x\log x).$$ Here $\theta(x)=...
1
vote
1answer
39 views

Asymptotics of a series involving cos integral functions

I'm looking for the asymptotic expansion( or value ) of the following function \begin{equation} F[y,t] = \sideset{}{'}\sum_{n \in \mathbb{Z}}\text{Ci}\big[\frac{n^2}{t}\big] - \text{Ci}\big[\frac{(n+...
4
votes
1answer
70 views

Asymptotic behavior of an integral involving the gamma function

I'm trying to obtain an asymptotic large-$k$ approximation for the integral $$I(k) := e^{-k^2}\int_0^1 \frac{(1 + \xi^2)\Gamma(0, \xi^2 k^2) - 2\Gamma(0, k^2)}{1 - \xi} d\xi$$ where $\Gamma$ is the ...
4
votes
3answers
2k views

How to show $\sum\limits_{i=1}^n\log\left(\frac{n}i\right)= \Theta(n)$?

Is the sum from i=1 to n for log(n/i) = Θ(n)? Im studying for a test and appreciate your help. This is what I did: and got something else $$\sum_{i=1}^n \log(n/i)=\sum_{i=1}^n[\log n-\log i]=\left(\...
6
votes
2answers
166 views

Asymptotics of $\sum\limits_{n=2}^\infty \frac{x^n}{(\log n) n!}$ as $x\to\infty$

I believe, based on numerical evidence, that $$\sum_{n=2}^\infty \frac{x^n}{(\log n) n!} \sim \frac{\exp(x)}{\log(x)}$$ as $x\to\infty$. However, I am not sure how to prove this. What would be a good ...
1
vote
0answers
31 views

Does asymptotic expansion of Whittaker function $W_{\lambda , \mu}(z)$ exist for $|\lambda| \to 0$?

Suppose Whittaker function $$ \tag 1 W_{\lambda , \mu}(z) $$ Does some asymptotic expansion exist for the case $|\lambda| \to 0$? I'm interested not in the case of $\lambda = 0$, but in the case of ...