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
0answers
99 views

Asymptotics of an integral

Consider an integral $$ I(x) = \int\limits_{\mathbb{R}^n} e^{i\xi x } \delta(\xi^2-k^2)\chi( (\xi-k,\gamma)) \, d\xi $$ where $x, k, \gamma \in \mathbb{R}^n$, $|\gamma| = 1$ and $(x,y)\equiv xy = ...
0
votes
1answer
547 views

Interesting Recurrence Relation $T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n$

I found an interesting recurrence that I do not know how to solve. I think this has to do with quicksort with pivots at rank $\sqrt{n}$. I do not know how to approach this problem nor found any ...
0
votes
1answer
82 views

WKB approximation question

I was reading some stuff on asymptotic analysis, but how do you get from the 1st line to the 2nd line? $y \sim \frac{1+x}{2\lambda}\exp\left(\frac{\lambda x}{1+x}\right) - ...
4
votes
2answers
1k views

Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , without (!) the master method

Given the Recurrences $$T(n)=T(n/2)+2^n$$ and $$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$ Remark : $T(n)=1$ for $n\le 3$ I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ ...
2
votes
1answer
292 views

Method of matched asymptotic expansions

Consider the equation $(x+1-\epsilon)\frac{dy}{dx}+(1-\frac{1}{4}\epsilon^2y)y=2(1-\epsilon x)$ with $y(1)=1$. I am interested in finding an asymptotic expansion for the inner solution so I put ...
2
votes
1answer
799 views

properties of a real analytic function

If there are a radius $r>0$ and constants $M,C\in\mathbb R$ for all $y\in U$ with $$|\partial^if(x)|\leq M\cdot i!\cdot C^{|i|}\space\space\space\space \forall x\in\mathbb B_r(y),i\in\mathbb ...
1
vote
1answer
1k views

Big-O notation always holds for this two functions?

For two any functions $f(n)$ and $g(n)$ always holds: $f(n) = O(g(n))$ or $g(n) = O(f(n))$ Right? Thanks
5
votes
1answer
251 views

expansion of $\int_0^\infty\left(\frac{\sin t}t\right)^p\mathrm dt$ in inverse powers of $p$

This question relates to this answer I gave to a question about the integral $$\int_0^\infty\left(\frac{\sin t}t\right)^p\mathrm dt\;.$$ I derived an expansion in inverse powers of $p$ and then ...
3
votes
1answer
306 views

Disproving a big O equation

As a homework assignment I am trying to prove/disprove the next statement: Let $f(x)=O_a(g(x))$, then $\forall A,B\in\mathbb{R}\rightarrow A\cdot f(x)=O_a(B \cdot g(x))$ Which I think is wrong ...
1
vote
0answers
76 views

Describe growth of $\epsilon n$

For all $\epsilon$ we have that $f(n)\le \epsilon n$ where n is a natural number. What can we say about the growth of $f(n)$? Clearly $f(n)=O(n)$, can we say anything sharper?
1
vote
1answer
511 views

Big O Notation question

I am trying to understand the Big-O and little-O notation, so I plotted 2 graphs which I have posted below, but I still dont really get the concept of it. What exactly does the ...
1
vote
0answers
53 views

Asymptotic bounds: $\ll$ vs. $\ll_{\epsilon}$?

I am feeling a bit slow today. In Analytic Number Theory it is usual to express asymptotic bounds by specifying the relation of the constant to a specific variable, i.e. $\log n \ll_\epsilon ...
2
votes
2answers
2k views

Why is $\log(n!)$ $O(n\log n)$?

I thought that $\log(n!)$ would be $\Omega(n \log n )$, but I read somewhere that $\log(n!) = O(n\log n)$. Why?
4
votes
1answer
128 views

With probability $o(1)$

I am not sure how to read little/big O expressions in probability theory: What does a statement like "with probability $1-o(1)$" mean? Does it mean with high probability?
0
votes
1answer
108 views

Explicit Big-$\mathcal{O}$ proof with predicate logic

For my newest homework I have given two functions $h,h^+:\mathbb{N}\to\mathbb{R}$ with $h(n)=n^{(-1)^n}$ and $h^+(n)=h(n+1)$. I have to proove that $h^+(n) \not\in\mathcal{O}(h(n))$ with an explicit ...
0
votes
1answer
99 views

Simple question about an asymptotic equality

Could someone please explain the second equality in Conjecture 1.1: http://arxiv.org/pdf/math/0501313v2.pdf ? (reproduced below) $(1+o(1))n^22^{1-n}=\left(\frac{1}{2}+o(1)\right)^n$ Initially, I ...
5
votes
2answers
837 views

Asymptotic expansion of integral involving modified Bessel-function

I would like to obtain the asymptotic expression for $\alpha \to \infty$ of the following integral $$I(\alpha)=\int_0^\infty\!dx\,x (1 - \cos[2\alpha K_0(x)]) = \int_0^\infty\!dx\, 2x \sin^2[\alpha ...
2
votes
1answer
61 views

$f \in O(g)$, iff $\limsup_{n\to\infty}|\frac{f(n)}{g(n)}| < \infty $

Given the functions $f$, $g$: $\mathbb{N} \to \mathbb{R}$ I have to prove that, $f \in O(g)$, iff $\limsup_{n\to\infty}|\frac{f(n)}{g(n)}| < \infty $ How can I prove it formally (at best using ...
1
vote
3answers
301 views

Asymptotic formula for the logarithm of the hyperfactorial

Background: I was trying to derive an asymptotic formula for the following: $$\sum_{m\leqslant n}\sum_{k\leqslant m}(m\ \mathrm{mod}\ k),$$ which I think I succeeded in doing (I will skip some steps ...
1
vote
2answers
83 views

Simplifying a logarithm of a little-o (circuit complexity)

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it: $o(2^n/n)\log(o(2^n/n) + n)$ I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + ...
3
votes
2answers
415 views

Sum of cubes of binomial coefficients

I reduced a homework problem in combinatorics to giving an asymptotic estimate for $\sum_{k=0}^n{n \choose k}^3$. I assume Stirling's approximation can help, but I'm not experienced with making ...
1
vote
3answers
420 views

Show that $2^n=O(n!)$

Show that $2^n=O(n!)$ Proof: By definition of Big-O, $\exists$ constants $c$ and $n_0$ such that $2^n \le cn!$ $\forall $ $n \ge n_0$. For a large $n$, since $$2^n = \underbrace{2 \cdot 2 \cdot ...
0
votes
0answers
63 views

Question about an asymptotic analysis proof in Ball Collision Decoding paper.

On page 21 of Daniel Bernstein's paper "Smaller decoding exponents: ball-collision decoding" he presents a proof that I have a few questions about. $P,Q,R,L$ and $W$ are all positive and close to ...
3
votes
0answers
92 views

Products of primes of the form $an + b$

What is the asymptotic order of numbers divisible by no primes except those of the form $an+b$ ($a$, $b$ fixed)? Surely (except for the trivial cases) they are of order strictly between that of he ...
2
votes
1answer
58 views

Finding an equivalent of $ u_{n}=\prod_{k=1}^{n} k^k $

I would like to find an equivalent of: $$ u_{n}=\prod_{k=1}^{n} k^k $$ I managed to find and asymptotic expansion of $ \ln(u_{n}) $ whose precision is $ o(n) $: $$ ...
0
votes
1answer
496 views

Improving Gift Wrapping Algorithm

I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points. ...
0
votes
1answer
306 views

Asymptotic notation - some equations.

i have a problem with proof one of this facts: $2^{2^n}$ = $\Theta (n^n)$ or $2^{2^n}$ = $O (n^n)$ or $2^{2^n}$ = $\Omega (n^n)$ and to proof one of this: $(n^n)$ = $\Theta (2^{2^n})$ $(n^n)$ = ...
1
vote
1answer
54 views

Finding an equivalent of $u_{n}-u_{\infty} $ where $u_{n}= \sum_{k=1}^{n} \frac{n}{n^2+k^2} $

I would like to find an equivalent of $$ u_{n}-u_{\infty}=\sum_{k=1}^{n} \frac{n}{n^2+k^2}-u_{\infty} $$ Using Riemann sums, it is easy to show that: $$ u_{n} \sim \frac{\pi}{4}=u_{\infty} $$ ...
0
votes
1answer
193 views

How one can prove $o(g(n)) \cap \omega (g(n))$ is empty?

From definition of $o$ and $\omega$ one states that $0 < c_1\cdot g(n) < f(n)$ for $n > n_0$ and some $c_1$ and another states that $0 < f(n) < c_2\cdot g(n)$ for $n > n_1$ and some ...
3
votes
0answers
336 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 ...
0
votes
1answer
3k views

Prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$ [duplicate]

Possible Duplicate: how can be prove that $\max(f(n),g(n)) = \theta(f(n)+g(n))$ How to prove $max(f(n),g(n)) = Θ(f(n)+g(n))$?
1
vote
2answers
243 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
2answers
343 views

Is this time complexity example correct?

This is probably not the best worded question but here goes. I've been reading a text book trying to get my head around time complexity. I understand the most of it, but this example has threw me. ...
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 ...
4
votes
1answer
704 views

Variations on the Stirling's formula for $\Gamma(z)$

I am currently reading some material that makes heavy usage of Hypergeometric functions, and there is one particular point about applying Stirling's approximation to various terms consisting of ...
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 ...
25
votes
1answer
778 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
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
138 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 ...
1
vote
2answers
290 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 ...
2
votes
1answer
333 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 ...
5
votes
2answers
284 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
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 ...
0
votes
0answers
563 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 ...
4
votes
2answers
120 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
votes
1answer
147 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 ...
0
votes
0answers
109 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 ...
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, ...
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)$$ ...