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

learn more… | top users | synonyms (1)

3
votes
0answers
305 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
2
votes
3answers
2k views

Help proving that $(n+a)^b = \Theta(n^b)$

Please you apologize me by my English. I don't know how make that: $$(n+a)^b = \Theta(n^b), b > 0$$ I know, I must to find two constants such that: $$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$ I ...
1
vote
2answers
242 views

Bounds on integral $x^{-a} \int_{1}^x y^{a-1} \exp(-y a) dy$

Consider the function $$ I(a,x) = x^{-a} \int_{1}^x y^{a-1} \exp(-y a) dy $$ where $x \geq 1$, and $a \geq 0$. I am not really interested in the parameter $x$, so define $$ I(a) = \sup_{x \geq 1} ...
1
vote
1answer
127 views

Asymptotics of a Cauchy Product

Suppose that two sequences $\{u_n\}$ and $\{v_n\}$ are such that $$ u_n \sim f(n) \qquad \text{and} \qquad v_n \sim g(n) \qquad (n \to \infty),$$ for some smooth functions $f,g$ which tend to ...
2
votes
2answers
123 views

Asymptotic behavior of integral of $\exp( \exp(-a y)/y - 1)$

I would like to compute the integral $$ I(a) = \int_{1}^{\infty} [\exp( \exp(-a y)/y) -1] dy $$ for $a > 0$. Note that the integrand is decaying very quickly, even more quickly than ...
2
votes
1answer
199 views

Coefficient growth in the power series $\sum u_n z^n = e^{1/(1-z)}$?

Let $\sum u_n z^n$ denote the power series of $e^{1/(1-z)}$. As our radius of convergence is $1$, it follows that $u_n$ exhibits sub-exponential growth. On the other hand, $\{u_n\}$ must grow ...
4
votes
2answers
136 views

'Error term' in zeta function [duplicate]

Possible Duplicate: What is the expression of $n$ that equals to $\sum_{i=1}^n \frac{1}{i^2}$? Asymptotic formulas for the n-th harmonic number are well-known: $$ \sum_{k=1}^n\frac1n=\log ...
5
votes
2answers
283 views

Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
1
vote
2answers
287 views

Abuse of big-O notation?

Given exam question: Algorithms A & B have complexity functions $f(n)=10^6n+3n^2$ and $g(n)=1-2^{-20}n^3$ respectively. [edit: It has been pointed out by Andre that the given complexity ...
25
votes
1answer
772 views

How many primes does Euclid's proof account for?

This is a passing curiosity, and I haven't found any duplicates, so I thought I'd share my thoughts. In the most basic (or at least the most famous) proof of the infinitude of prime numbers, due to ...
2
votes
1answer
325 views

Big-O, asymptotical dominance, asymptotical equivalence

Let $f(x)= 5x^3+x.$ A) I'm just learning the Big O notation, and my study materials indicate that since $f(x)$ is $O(x^3),$ $f(x)$ is asymptotically dominated by $x^3.$ B) On the other hand, I know ...
0
votes
0answers
547 views

Asymptotic equivalence?

Let there be two functions $f(x)$ and $g(x)$. If we consider $\lim_{x \rightarrow x_{0}} \frac{f(x)}{g(x)} = k$, we say that $k=1$, then $f(x)\sim g(x)$, $f(x)$ is equivalent to $g(x)$ as $x ...
0
votes
1answer
823 views

Asymptotic functions

Someone can help me to identify a function $f$ and a functon $g$ which statisfy the conditions specified below: $f(n) = \operatorname{O}(g²(n))$ $f(n) = \Omega(f(n)g(n))$ $f(n) = \Theta(g(n)) ...
1
vote
3answers
172 views

Maximum order of a sum of functions

I'm being introduced to the Big-O notation via Susanna Epp's Discrete Mathematics with Appplications 3rd edition. The following defintion is stated on page 519: Let f and g be real-valued functions ...
-1
votes
1answer
146 views

Big Omega equation

I am struggling still with this equations...from my class materials.... This time we deal with lower bound -> BIG OMEGA: I know that: $$\Omega(g(n)) = \{f(n) : \exists c, n_0 > 0\,\forall n\ge ...
4
votes
2answers
118 views

Asymptotics of products of primes

Let $P(n)=\{p \leq n: p\text{ is prime} \}$. For given $N$ and $n$, what's a good approximation for $|S(N,n)|$, where $S(N,n)=\{x<N: \forall p\text{ prime, s.t. }p|x \to p \in P(n) \}$. In other ...
1
vote
0answers
326 views

Convergence of $L^p$ norms

Given a measure space $X$ with its measure $\mu$, it can be shown (I'll provide a proof if asked for) that $\displaystyle \forall f \in L^\infty(X,\mu),~\textrm{if } \exists p_0:\forall q \geq p_0, ...
0
votes
0answers
108 views

Asymptotic equality

How can i prove this asymptotic equation? $$2n^n + 2n^{n+1} = 2n^n + \Theta(2^n) $$ The theorem says: $$ \Theta(g(n)) = \{f(n): \exists c_1, c_2, n_0 > 0\,\, c_1g(n) \le f(n) \le c_2g(n), \,\,n ...
20
votes
3answers
487 views

Asymptotic expression of an oscillatory integral

Consider the integral $$ f(\alpha,\beta)= \int_0^{2\pi}\,dx \sqrt{1- \cos(\alpha x ) \cos(\beta x)}$$ as a function of the two parameters $\alpha,\beta$. I am interested in the asymptotic behavior ...
3
votes
2answers
105 views

Is it possible to prove that a problem $P$ is decidable in $O(\phi)$ without providing an algorithm that decides $P$ in $O(\phi)$?

Phrased another way: Are there any problems that are known to be decidable in a better worst-case time complexity than the best known procedure?
2
votes
4answers
2k views

The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.

Trying to simplify the following expressions in $n$ to find its order of growth. I want to show the simplification separately from the order of growth $$\sum_{k=1}^{n} k \log k = \Theta(n^2 \log n)$$ ...
0
votes
1answer
107 views

Can a discrete function have an asymptote?

I have this function which approaches zero in discrete steps: $$\frac{1}{2^{int(x)}}$$ My question is that although this function shows asymptotic behaviour in that it approaches $$y=0$$ does it ...
0
votes
1answer
168 views

$\Theta$-notation of a logarithm

Given $H(x) = lg(f(n))$, where $f(n)$ is an asymptotically positive function, is it always true that if $f(n) = \Theta(g(n))$, then $H(x) = lg(\Theta(g(n)))$ $\Rightarrow H(x) = \Theta(lg(g(n)))$ ...
3
votes
1answer
151 views

Dilogarithm asymptotics for an exponential parameter.

So this question is about this dilogarithm function. Assume the argument $z$ is real then I want to show the formula $$\operatorname{Li}_2(e^{-z})=\frac{\pi^2}{6} + z\log z -z+O(z^2) $$ as $z$ ...
0
votes
1answer
614 views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
1
vote
1answer
66 views

Is it possible to store an integer in sub-logarithmic space?

The most intuitive method of representing an integer is in unary. For example, 10 can be represented as 0000000000, ----------, etc. This requires O(n) space. The most common method is slightly more ...
3
votes
1answer
152 views

Intuition behind growth rate of some functions

This one really crushed my intuition. Let say a function $f$ grows faster than a function $g$ if $ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty $ Which of the following functions grows the fastest ...
6
votes
1answer
179 views

Asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$

I'm looking for pointers as to how to evaluate the asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$ for large $n$ where $0<p<1$ is fixed. Any help is much appreciated.
3
votes
1answer
73 views

Asymptotics of a solution

Let $x(n)$ be the solution to the following equation $$ x=-\frac{\log(x)}{n} \quad \quad \quad \quad (1) $$ as a function of $n,$ where $n \in \mathbb N.$ How would you find the asymptotic behaviour ...
1
vote
2answers
247 views

Particular Use of Big O Notation

I'm reading a theorem that states "...Then for each $j$ and $\epsilon>0$, there exists $n\leq 2^{O(j/\epsilon)}$..." What exactly is the big-oh notation saying in this case? I guess it must be ...
6
votes
2answers
1k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
4
votes
1answer
475 views

How does one integrate Landau symbols?

I have some big O()'s in an integral. How can i compute or estimate such an integral?
0
votes
1answer
295 views

Big Oh notation/estimation

I have recently encountered a series of perturbation problems in which the Big Oh notation is used frequently. Since I have not encountered this notation before, I am a little bit confused about it. ...
4
votes
2answers
462 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
2
votes
2answers
154 views

What do I get by adding $\Theta(n)$ and $O(n)$?

I know that that $f(n) = O(n)$ means that $n$ is the asymptotically upper bound of $f(n)$ and that $\Theta(n)$ is the asymptotically tight bound of $f(n)$. Still, I'm wondering whether I am allowed to ...
1
vote
1answer
112 views

Theta notation from the inequality $c_1lg(n) \leq lg(k) \leq c_2lg(n)$ [duplicate]

Possible Duplicate: tight bounds from a certain inequality Consider the inequality $$ c_1lg(n) \leq lg(k) \leq c_2lg(n),\text{ for } n \geq n_{0} $$ With $c_1,c_2,n_0 > 0$, $lg(k) = ...
3
votes
0answers
85 views

Asymptotics of Riemann-Lebesgue type integral

How to show that for $u \in L_{\mathbb{C}}^2$ and $a>0$, $$\int_0^a u(t) \sin{\sqrt{\lambda}t} \,dt = o(e^{|Im\sqrt{\lambda}|a}),\text{ as } |\lambda| \rightarrow \infty$$ Note that $\lambda$ ...
-1
votes
3answers
91 views

Prove $(\log_2n)^{100} = \mathcal O(n^{1/10})$

On my homework: prove that $$(\log_2n)^{100} = \mathcal O(n^{1/10})$$ Any ideas are appreciated.
2
votes
2answers
135 views

determining the order of expressions, eg: $\sqrt{\varepsilon(1-\varepsilon)}$

I have to determine the order of loads of expressions as $\varepsilon \to 0$. Can you help me by giving me an example of how to find the order of $\sqrt{\varepsilon(1-\varepsilon)}$.
1
vote
0answers
105 views

asymptotic behaviors

Can you help me find the leading asymptotic behaviors about the irregular singular point $x=0$ of $x^4 \frac{d^2y}{dx^2}+ \frac{1}{4}y=0$. I do not know where to start with this
1
vote
2answers
167 views

Showing something is an asymptotic sequence

I need to show that $\phi_n(z)=\ln(1+z^n)$ as $z \rightarrow 0$ is an asymptotic sequence, i.e. to show that $$\lim_{z\rightarrow 0}\frac{\phi_{n+1}(z)}{\phi_n(z)}=0.$$ Is it sufficient for me to say ...
2
votes
1answer
127 views

Order of logarithmic functions as $x \rightarrow 0$

I am trying to find the order of logarithmic expressions as $x \rightarrow 0$. For example I can find that $\ln(1+x) = \mathcal{O}(x)$ and $\ln(1+x) = \mathcal{o}(1)$. But when dealing with more ...
0
votes
1answer
135 views

Order of trig functions as $x \rightarrow 0$

In my notes it was given that as $x\rightarrow 0,$ $$\frac{x^{3/2}}{1-\cos x} = \mathcal{O}(x^{-1/2})$$ It didnt give any explanation, so I was wondering what would the "method"/"intuition" be ...
3
votes
3answers
347 views

The order of $\sqrt{\epsilon(1-\epsilon)}$ and $4\pi^2\epsilon$ as $\epsilon \rightarrow 0$?

I was reading on the big O/little O notation etc. and I understand the definitions, but how exactly would I use it to find the order of an expression/function? I am asked to determine the order of ...
3
votes
1answer
536 views

How does big-Oh notation work?

I am reading this document. In this article after defining strong derivative Knuth goes on to calculate derivative of $x^n$. There he uses definition of strong derivative to expand ...
3
votes
1answer
245 views

(Not) Surprising Result on Natural Numbers as Sum of $k$-Almost Primes

I started with the following idea: Let $P_k$ be the infinte set of all $k$-almost primes. The counting function for $k$-almost primes less than $x$, is $\displaystyle \pi_k(x)\sim\frac{x}{\log ...
0
votes
1answer
224 views

arithmetic between limits

I need find $\lim\limits_{x\rightarrow\infty}( x^3-x^2)=L$. In this case, I ended up with infinity minus infinity. But I do know $x^3$ is always greater than $x^2$ for $x\ge1$ and the difference ...
14
votes
2answers
354 views

On the Limit of Stirling's Approximation

I have recently proven the following curious identity: For real $x \geqslant 1$, \begin{align} \lfloor x \rfloor! = x^{\lfloor x \rfloor} e^{1-x} e^{\int_{1}^{x} \text{frac}(t)/t \ dt} \end{align} ...
11
votes
1answer
2k views

Derivation of asymptotic solution of $\tan(x) = x$.

An equation that seems to come up everywhere is the transcendental $\tan(x) = x$. Normally when it comes up you content yourself with a numerical solution usually using Newton's method. However, ...
3
votes
0answers
145 views

How to solve equation involving binomial coefficient?

I'm reading this paper which says If we have $$ \binom n d p^{\binom d 2} = 1 $$ where $ 0 < p \le 1$, then $$ d = 2 \log_bn - 2 \log_b \log_b n + 2 \log_b\left(\frac 1 2 e\right) + 1 + O(1) ...