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
1answer
302 views

All asymptotes of $f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$

Find the number of all possible asymptotes of: $$f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$$ Since we know $\sqrt{ax^2+bx+c}\approxeq \sqrt{a}\big|x+\frac{b}{2a}\big|$ when $(x\rightarrow\pm\infty)$ so, ...
2
votes
1answer
80 views

What is the value of this summation in Big O terms?

I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below: $$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$ What will be the Big O ...
4
votes
1answer
178 views

If $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$?

This may be a dumb question, but if $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$? I can think of a few counter examples, like $n\in O(n^2)$ and obviously $n^2\notin O(n)$, but one counter example doesn't ...
1
vote
1answer
90 views

Estimate cardinality of the set

Prove that: $$\left|\left\{ \langle a,b \rangle\in \mathbb{N}\times\mathbb{N}:a^2+b^2\le n \right\}\right|=\frac{\pi}{4}n+O(\sqrt{n})$$ I heard something about that the number of lattice points ...
5
votes
1answer
72 views

Estimate sum with a very small error

Estimate sum: $$\sum_{i=1}^{n}\frac{i}{n^2+i}$$ with an absolute error $O\left(\frac{1}{n^2}\right)$ So far, estimation with integrals was sufficient for me, but here the error has to be very ...
1
vote
1answer
124 views

convergence of an oscillatory integral

Let $\alpha$ be real numbers and let $f\colon\mathbb{R}\to \mathbb{C}$ be a function in $L^2 (\mathbb{R})$ (actually smooth and compactly supported, but this doesn't seem to be relevant). I am ...
3
votes
2answers
71 views

Asymptotic analysis of a recurring sequence

Let $(u_n)$ be a sequence defined by: $$\begin{equation} \left\{ u_0 \geq 0 \\ \forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}} \right. \end{equation}$$ I'd like to prove that when $n ...
2
votes
2answers
296 views

A systematic way to estimate the cardinality of a set

Let me take the following set as an example: \[ A = \lbrace \langle a,b \rangle \in \mathbb{N} \times \mathbb{N} : a^2 + b^2 \leq n \rbrace . \] One approach would be to notice that $A$ is the set ...
3
votes
3answers
188 views

A couple of asymptotics exercises

Recently I've been following the chapter on asymptotics in Concrete Mathematics. The subject matter of it is relatively new to me though and I'm having some difficulties dealing with asymptotic ...
0
votes
0answers
41 views

Estimating the recurrence $T(n,i) = (\lfloor\frac{n-i}{i}\rfloor \cdot i ) + T(i + (n \operatorname{rem} i), (n \operatorname{rem} i))$

Given $i < n/2$ and denoting $[x]$ to be an integer part of $x$ (floor$(x)$) and $(a \operatorname{rem} b)$ to be a reminder when $a$ is divided by $b$. $$ T(n,i) = ...
0
votes
3answers
252 views

Maple Error on Asymptotic Analysis of $\ln(n)!$

In Maple, the command asmypt($f$,$x$) computes the asymptotic expansion of the function $f$ with respect to the variable $x$ (as $x \rightarrow \infty$). The command asympt(ln(n)!,n); gives the ...
0
votes
0answers
57 views

Estimating cardinality of a set

Estimate |$\{<a,b,c> \in \mathbb{N}:a^2+b^2+c^3 \le n\}$| with absolute error of $O(n)$.
2
votes
1answer
63 views

Flawed twofold induction on an inequation (but where?)

The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...
2
votes
1answer
98 views

Little-o vs. asymptotic equivalence

As big- and little-o notation are a little too technical to me, I prefer an expression with asymptotic equivalence ($\sim$). However, how does one "translate" this expression to an asymptotic ...
2
votes
1answer
132 views

Two asymptotics problems

Problem 1. Estimate $\displaystyle \sum_{i=1}^n \frac{\ln i}{\sqrt{i}}$ with an absolute error $O(1)$. Problem 2. Estimate: $$\left|\left\{ \langle a,b,c \rangle\in \mathbb{N}_+^3 : abc\le n ...
2
votes
2answers
222 views

Estimation of sums with number theory functions

Problem 1. Let $d(k)$ denote the number of divisors of $k\in\mathbb{N}$. Prove that: $$\sum_{k=1}^{n}d(k)=n\ln n +O(n)$$ Problem 2. Show estimation below: ...
0
votes
1answer
52 views

Asymptotic behavior of a sequence based on a subsequence II

Let $\{a_{n}\}$ be a non-increasing sequence of positive numbers. if for some positive integers $l,p$ and $R>1$ we have $a_{(ln)^{p}}=O(R^{-n})$ as $n\to\infty$, what can we say about the behavior ...
3
votes
3answers
359 views

Predicting the next vector given a known sequence

I have a sequence of unit vectors $\vec{v}_0,\vec{v}_1,\ldots,\vec{v}_k,\ldots$ with the following property: $\lim_{i\rightarrow\infty}\vec{v}_{i} = \vec{\alpha}$, i.e. the sequence converges to a ...
3
votes
1answer
90 views

matrix “flag” clearing

I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example: $$ ...
1
vote
1answer
735 views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
2
votes
0answers
91 views

Growth of number of distinct elements

Let $A_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n$. Let $B_k$ be a random ...
2
votes
2answers
194 views

Help with the integral for the variance of the sample median of Laplace r.v.

When we draw $n$ samples of Laplace-distributed random variable such that $n=2k+1$ and the location parameter is zero, the median $x$ (or the $k$-th order statistic) has the following p.d.f.: ...
0
votes
1answer
105 views

An argument to prove asymptotic expansions

I have a real number $I_h$ depending on a small parameter $h>0$. I want to show that it has an asymptotic expansion in integer powers $h$, i.e. there exists a sequence $(J_k)_{k}$ such that $$ I_h ...
0
votes
2answers
973 views

Master theorem solving

I'm starting to study the master theorem, why does something like $$T(n) = aT(n/b)+f(n)$$ solves to $$f(n)^{\log_ba}$$ ? I'm a bit confused on the resolution
9
votes
3answers
328 views

Approximation of elements in arithmetic progressions by logarithms of integers

For fixed $a,b,c \in \mathbb{R}$ with $ac \neq 0$, it seems to me that one can find an increasing sequence of integers $\{\alpha_n\}$ such that the quantity $c \log \alpha_n$ becomes arbitrarily close ...
0
votes
1answer
55 views

Estimates of Gaussian Logarithms

I've been implementing logarithmic number system and I came across these functions called Gaussian logarithms: $f(x) = \log(1 + e^x)$. $g(x) = \log(e^x - 1)$ for $x > 0$. $h(x) = \log(1 - e^x)$ ...
1
vote
3answers
1k views

What does asymptotically optimal mean for an algorithm?

What does it mean to say that heap sort and merge sort are asymptotically optimal comparison sorts . I know What the Big O , Big Omega($\omega)$ and Theta($\theta$) notations are and I also know ...
0
votes
3answers
203 views

O-notation property - sum of the first n powers growth

I read here that in the tenth property: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/latex/complexity.pdf The sum of the first $nr^{th}$ powers grows as the $(r+1)^{th}$ power This is not very ...
1
vote
1answer
78 views

Complete expansion of Laplace integral

Let $\varphi \in C^\infty (\mathbb R^n ;\mathbb R)$ such that 1) $\varphi(0)=0$ 2) $\varphi(x)>0$ on $\mathbb R^n\setminus 0$ 3) $\text{Hess}_{\varphi}(0)>0 $ and let $B_1(0)$ be the ...
2
votes
1answer
125 views

Monotone Sequence & Big-O Notation

I was thinking about the following problem: Consider a sequence $a_n \to 0, a_n >0$ which is monotone, i. e. $a_n\ge a_{n+1}$. Now suppose for every $C>0$ there is a subsequence $n(k)$ such ...
3
votes
1answer
193 views

Laplace's method with unknown exponent.

Given the integral: $$I = \int_0^a{e^{-\lambda g(x)}f(x)dx}$$ Where $g(x)$ and $f(x$) are both low order positive polynomials, and $\lambda \gg 1$, Laplace's method is commonly used to approximate ...
0
votes
1answer
874 views

Show that $k\ln k \in \Theta(n)$ implies $k \in \Theta(n/\ln(n))$?

It is exercise (3.2-8) from Introduction to Algorithms book. I need help to solve it. I am confused by the fact that there are two parameters. Because usually one parameter is used. There is related ...
11
votes
3answers
365 views

The boundedness of an integral

Is there a constant $C$ which is independent of real numbers $a,b,N$, such that $$\left| {\int_{-N}^N \dfrac{e^{i(ax^2+bx)}-1}{x}dx} \right| \le C?$$
1
vote
1answer
158 views

Justifying O-estimate of Poisson's Kernel as $x$ goes to the boundary

This question stems from a step of a proof in this paper: http://www.cmap.polytechnique.fr/~ammari/papers/04AKS.pdf The question itself I didn't feel to be "research level" as it is only an ...
2
votes
1answer
84 views

Asymptotic behavior of a sequence based on a subsequence.

Let $c\in(0,1)$, $m\geq 1$ be positive integer and $\{a_{n}\}$ a decreasing sequence of positive real numbers. Suppose that $$a_{n^{m}}\leq K c^{n}n^{-m/2}, \forall n\in\mathbb{N}, $$for some ...
1
vote
1answer
640 views

How to proof $n^2+n \in \Theta(n^2)$?

It stands to reason that $n^2+n \in \Theta(n^2)$. But how can I formally proof it? I tried next way: Generalized to $$f(n)+o(f(n)) \in \Theta(f(n))$$ Separated to $$\tag{1} f(n)+o(f(n)) \in ...
4
votes
1answer
769 views

About the asymptotic formula of Bessel function

For $ \nu \in \Bbb R$, I want to prove the well-known formula $$ J_\nu (x) \sim \sqrt{\frac{2}{\pi x}} \cos \left( x - \frac{2 \nu +1}{4} \pi \right) + O \left( \frac{1}{x^{3/2}} \right) \;\;\;\;(x ...
3
votes
6answers
525 views

Proof by contradiction that $n!$ is not $O(2^n)$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find ...
0
votes
1answer
66 views

Decay for the tail of a series.

Let $p>1$. I would like to have an estimate for the decay of the sequence $s_{n}=\sum_{k=n}^{\infty}k^{-p}$. Does anyone know of a bound of this type in the literature? Thanks!
0
votes
1answer
129 views

How to compare big numbers that are outcome of different functions.

How is the best way to compare big numbers? They are result of two functions with different asymptotic growth. For example: Googleplex which is $10^{{10}^{100}}$ to $1000!$
3
votes
0answers
57 views

Is there a common name for $O(x^{cx})$ type functions?

Is there a common name for the growth rate of functions that are asymptotically on the order of $x^{cx}$, for some $c$? The term super-exponential is much too general. The factorial function grows in ...
1
vote
2answers
104 views

Formally prove/disprove that $\sqrt{n}o(\sqrt{n}) = o(n)$

I'm wondering how to formally show that $\sqrt{n}o(\sqrt{n}) = o(n)$. The problem I'm having is that I don't really know how to formally resolve the multiplication on the LHS. It would be ...
2
votes
3answers
131 views

Show that $(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$ for $x\rightarrow \infty$

So I'm trying to show that for $x\rightarrow \infty$: $$(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$$ So these complicated big-Oh expressions are clearly going to be a recurring theme in my book, and I ...
3
votes
2answers
129 views

Help Proving that $\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$ for $t\geq 1$

I'm trying to prove the asymptotic statement that for $t\geq 1$: $$\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$$ I know that $(1+\frac{1}{t})^t$ converges to $e$ and the right ...
2
votes
1answer
63 views

Interpretation of $f(n) \in o(n)$

Suppose that some function $f(n)$ is in $o(n)$. Is it fomally correct to say that there exists an $N$ such that for all $n \ge N$ it holds that $$f(n) \le \frac{c n}{g(n)}$$ where $c>0$ is a ...
1
vote
1answer
62 views

Minimizers of an expression with little O notation

Suppose that $f(x) = o(\sqrt{x})$ as $x\rightarrow\infty$ and let $x^*(a)$ denote the minimizer of $f(x) + a^{3/2}/x$, that is, the value of $x$ that minimizes said expression (assuming such a value ...
6
votes
1answer
3k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
3
votes
1answer
221 views

Asymptotics of an expression of the root of a polynomial

Given that $x_0$ is the unique positive solution of $(2-x)^{n+1}=x(x+1)\cdots(x+n)$, try to find the asymptotic value of $$ M=\prod_{k=0}^n\left(\frac{k+2}{k+x_0}\right)^{k+2} $$ with absolute error ...
1
vote
2answers
175 views

Singular Perturbation Problem? Asymptotics?

I am in the midst of solving this equation $\epsilon \ddot{y}+\dot{y}+1-\frac{1}{(y+1)^{2}}=0$ with the boundary condition $y(0)=1$ and $\dot{y}(0)=-1$ and $\epsilon$ is small. To start off with, I ...
2
votes
0answers
76 views

Two terms approximation of a recurrence [closed]

Find an approximation up to the second term of $z_n$ where $z_{n+2}=z_{n+1}+\sqrt{n}z_{n}$ and $z_{2}=2z_{1}>0$.