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

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
0
votes
1answer
44 views

Arrange the functions… [closed]

Arrange in increasing order the following functions: $$n^2 , n! , \lg n , (\frac{3}{2})^n , e^n , n \lg n , 1, (\lg n)^2, 2^{2n}=4^n$$ Could you give me a hint how to do this?
2
votes
0answers
18 views

Is $\frac{x^2(1-p)}{(n-x+1)p}\leq \frac{x^2}{(n-x)p}=O((np)^{-1})=o(1)$?

Is it true that for $n \rightarrow \infty$, $p \gg n^{-1}$, $0<p<1$ and $x=O(1)$, $$\frac{x^2(1-p)}{(n-x+1)p}\leq \frac{x^2}{(n-x)p}=O((np)^{-1})=o(1)?$$
1
vote
1answer
20 views

Big-Theta:What happens if $\displaystyle{a_d<0}$?

If $\displaystyle{f(n)=an^2+bn+c}$ with $\displaystyle{a>0}$ then $\displaystyle{f(n)=\Theta{(n^2)}}$. Generally, if $\displaystyle{f(n)=\sum_{i=0}^{d}a_in^i}$ with $\displaystyle{a_d>0}$ then ...
1
vote
0answers
17 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
2
votes
2answers
54 views

Show that $\frac{1}{2}n^2-3n=\Theta{(n^2)}$

Show that $$\frac{1}{2}n^2-3n=\Theta{(n^2)}$$ $$$$ $\displaystyle{\frac{1}{2}n^2-3n=\Theta{(n^2)}: \\ \exists c_1, c_2 >0 , \ \ \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0 \\ ...
4
votes
1answer
75 views

Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial

Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions. It only gives two ...
2
votes
0answers
50 views

perturbation theory solution of forced Duffing's equation

Question: Find the leading order of the asymptotic expansion for large t: $\frac{d^2x}{dt}+\varepsilon\beta\frac{dx}{dt}+x+\varepsilon x^3=Fcos(\frac{1}{3}\big(1+\varepsilon\omega)t\big)$ I have ...
1
vote
1answer
66 views

Meaning of $\sim$?

I often read $f(x) \sim g(x)$ and I wonder what the Standard Interpretation of this $\sim$ is. It seems to mean something like asymptotically equally distributed, something like $f(x)=g(x)(1+o(1))$. ...
6
votes
3answers
147 views

Asymptotic behaviour of the integral of the quadratic mean of the coordinates on the hypercube

I have to compute the limit $\lim_{n\to +\infty}I_n$, where: $$\qquad I_n=\int_{[0,1]^n}\sqrt{\frac{1}{n}\sum_{i=1}^n x_i^2}\,d\mu.$$ I believe that its value is just $\frac{1}{\sqrt{3}}$, since the ...
2
votes
1answer
43 views

How can we show that if $f(n) = O(n^2)$, then $ f(n) = O(n^3)$

I'm looking at the 'positive constants' definition, but just not seeing how to go from here to there.
1
vote
1answer
29 views

Using Stirling's approximiation to show that $(\log(\log n))!$ is $O(n^k)$

I am trying to show the following: Prove, using Stirling's approximiation, that $(\log(\log n))!$ is $O(n^k)$ for some positive constant $k$. Stirling's approximation is $$n!=\sqrt{2\pi ...
2
votes
0answers
32 views

Asymptotic analysis of certain multiple integration of power functions

Let $t_1,\ldots,t_m>0$, and $m\ge 4$ be an even integer. Consider the function: $$ f(a,b;\mathbf{t})=\int_0^{t_1}\ldots\int_0^{t_m} |x_1-x_m|^a |x_2-x_1|^b |x_3-x_2|^a |x_4-x_3|^b \ldots ...
0
votes
0answers
46 views

Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
28 views

Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms

I want to better understand the following concepts: "n!", "e^n". I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...
23
votes
1answer
425 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
0
votes
1answer
18 views

Does this function go to zero faster than the norm of its argument?

Assume $f:\mathbb R^2\to\mathbb R$ is such that for all $\varepsilon>0$ exists $\delta>0$ such that, whenever $||x||<\delta$, also $||f(x)||<\varepsilon^2$. Can we see that $f$ is ...
0
votes
1answer
37 views

asymptotic notations and their running time [closed]

I know that for $f(x) = O(g(x))$ running time $T(n) = O(n^3)$ $f(x) = \Omega(g(x))$ running time $T(n) = \Omega(n^2)$ but what is the $T(n)$ for $f(x) = Θ(g(x))$ ? Also tell me running time for ...
1
vote
1answer
65 views

The Asymptotic Expansion of The Exponential Integral

I was reading R. Wong's book on Asymptotic Approximations of Integrals, and I'm having problems with the derivation of the asymptotic expansion of the exponential integral which he defined as follows: ...
7
votes
3answers
502 views

Can asymptotes be curved?

When I was first introduced to the idea of an asymptote, I was taught about horizontal asymptotes (of form $y=a$) and vertical ones ( of form $x=b$). I was then shown oblique asymptotes-- slanted ...
0
votes
1answer
28 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
7
votes
2answers
72 views

Asymptotically, how many random students do I have to mark before I've marked two consecutive students

Background The motivtion for this question comes from observations made by a colleague while he was marking homework and recording the marks this year. His procedure for recording the marks is as ...
2
votes
1answer
40 views

Asymptotic approximation for the r-associated Stirling numbers of the second kind

It is well know that for fixed $k$ the asymptotic approximation for the Stirling numbers of the second kind is given by $\frac{k^n}{k!}$. Does such simple asymptotic expression also exist for the ...
1
vote
2answers
30 views

Asymptotic notation: A function is Θ-Notation

H. Cormen, Exercise 3.1-2 The following statement is true? If yes, prove that it is true. $$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$ I tried to expand $(n+a)^b$ using the Binomial theorem, but ...
0
votes
1answer
34 views

Master Theorem , Polynomial, recurrences

Going through Master's theorem for recurrences but I am seriously confused as what it means when we say that function f(n) is polynomially greater than function g(n) (Case 3) and how can one check ...
1
vote
0answers
24 views

Asymptotic behavior of oscillatory Hilbert transform

Does anyone know what is the leading term in the asymptotics of $$ P.V. \int\limits_{ -\infty }^{ +\infty } \frac{e^{i \lambda x^3 } f( x ) dx }{ x }, $$ as $ \lambda \to +\infty $? Assume $ f \in ...
1
vote
2answers
31 views

math rules when having 2 variables in Big-O

I came across the following in some lecture notes: O(log n) + O(log m) = O(log n + log m ) = O(log (m + n)) that last step to ...
0
votes
0answers
38 views

Growth rate of integral

My apologies, I have no idea how to make the title more specific without putting the whole question in there. On p. 60 of Montgomery and Vaughan they state \begin{equation} 2\int_e ^x \frac{1 + \log ...
1
vote
0answers
44 views

Sums of Power Law random variables

Suppose $F$ be a pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , ..., X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
0
votes
1answer
20 views

Asymptotic expansion of $z^{-x}$

Consider the function $z\mapsto z^{-x}$ for $x>1$ (real) and $z$ in the cut complex plane $\mathbb C\backslash\{z\leq 0, \text{ real}\}$. Does this function have an asymptotic expansion of the form ...
2
votes
1answer
35 views

Extrema of the Ratio of Consecutive Primes

Let $p_i$ denote the $i$th prime number. We know that $\frac{p_{n+1}}{p_n}\rightarrow 1$ as $n\rightarrow\infty$. Therefore, if we pick some real number $c>1$, there should be some positive integer ...
0
votes
1answer
18 views

First Order Approximation Taylor Series

I have the taylor series $f(z)=f(x_0)+(x-x_0)f'(z)+1/2(x-x_0)^2f''(z) ...$ and I am told that "As a first order approximation," $x-x_0$ ~ $\frac{f(x)-f(x_0)}{f'(x_0)}$ assuming $f'(x_0) \neq 0$ I ...
0
votes
1answer
28 views

Big-O Analysis: Max Bounded by the Sum

I have been asked to show that: $$ \mathcal{O}(Max\{ f(n), g(n) \}) = \mathcal{O}(f(n) + g(n)) $$ I have seen explanations of similar problems, but this is the first time I have encountered the ...
0
votes
0answers
51 views

Asymptotic complexity of $\sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$

I'm trying to examine the asymptotic complexity of $$f(m) = \sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$$ Question: How do you prove or disprove $f(m) \in \mathcal{O}(2^{2^m})$? Bonus ...
0
votes
1answer
34 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
6
votes
1answer
124 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 ...
2
votes
2answers
112 views

Calculate limit with factorial

I need to find the limit of this function..I thought about L'hôpital's rule, but can't seem to derive them both.. $$\lim_{n\rightarrow\infty} \frac{(2n)!}{(n!)^2}$$
1
vote
1answer
34 views

How on earth will anyone prove $n^3-3n^2+n-1=Θ(n^3)$

I know its homework question.Sorry for that.But i was solving all problems of Skiena and chapter and got stuck to this problem of 2nd chapter 2.10. Its easy to prove $n^3-3n^2+n-1=O(n^3)$ because ...
0
votes
0answers
26 views

Finding a leading order approximation for a system of ODE (multiple scales)

I need to find the leading order approximation which is valid for times $t=ord(\frac{1}{\epsilon} ) $ as $\epsilon \to 0$ to the solution $x(t,\epsilon)$ and $y(t,\epsilon)$ satisfying: ...
0
votes
1answer
32 views

Determine the realtions ($\mathcal{O}$,$\Theta$,$\Omega$ ) between $f(n) = \ln(n^{c} + n^{d})$ and $g(n)=\ln(n^{a} + n^{b})$

I am trying to determine the realtions ($\mathcal{O} $,$\Theta$,$\Omega$ ) between : $$f(n) = \ln(n^{c} + n^{d})$$ $$g(n)=\ln(n^{a} + n^{b})$$ Note: $a,b,c,d>0$ I need some advice how to use the ...
1
vote
3answers
114 views

A system of $n$ equations , how does it behave for growing $n$?

I read about the system of $n$ equations in the link below. I wonder how it behaves for growing $n$. Does it converge ? http://math.eretrandre.org/tetrationforum/showthread.php?tid=889 Here it is ...
0
votes
1answer
51 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
1
vote
0answers
32 views

Help understanding this approximation

In a paper that I'm reading, the authors write:- $$N_e \approx \frac{3}{4} (e^{-y}+y)-1.04. \tag{4.31}$$ Now, an analytic approximation can be obtained by using the expansion with respect ...
-1
votes
1answer
156 views

Asymptotic value of Fibonacci numbers

It is well known that $F_n\sim\frac{\phi^n}{\sqrt{5}}$, where $\phi=\frac{1+\sqrt{5}}{2}$. Does someone know a better estimate? With proof please. I'm trying to calculate the following limit: Let ...
0
votes
1answer
47 views

Can we say that $ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$?

Can we assert and proove that : $$ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$$ And What inequality relating two parts can be proved ?
3
votes
1answer
100 views

Asymptotic behavior of a sequence of integrals

I am interested in the asymptotic behavior of sequences $(I_n)$ and $(J_n)$ as $n \rightarrow \infty$, where $$I_n = \int_{1}^{\infty}\frac{e^{-nx^2}}{x^2}\, dx,$$ and $$J_n = ...
1
vote
0answers
22 views

asymptotics of the solution of an integral equation

Suppose we are given the integral equation $$ u(x;a) =v(x)+\int_0^a K(x,y)\,u(y;a)\,dy, $$ where $K(x,y)$ and $v(x)$ are known functions, and $a>0$ is a constant. What I am interested in is the ...
0
votes
2answers
45 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
4
votes
0answers
51 views

A general question of asymptotics

I am very desperately longing to know if there is a explicit relationship between $$F(n)=f(1)+f(2)+...+f(n)$$ and $$G(x)=\sum_{k=1}^{\infty}f(k)x^k$$ Assuming we can let $f$ be a sufficiently well ...
7
votes
1answer
209 views

First-term approximation for singular perturbation of ODE (with two turning points)

I'm reading "Introduction to Perturbation Methods" by Mark Holmes, and I came across an exercise that I don't know how to approach. As I decided to independently read this book, I have no ...