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

What are the bounds (upper and lower) for $|A+A|$?

Let $A$ be a finite set of real (or complex) numbers. If I consider sets with small sizes, we have that: If $A$ is the empty set, then $A+A$ is also empty. If $A$ is a singleton, then $A+A$ is ...
1
vote
2answers
46 views

Unusual Asymptotics Question

I want to prove the following$$n - 2\sqrt{n} = \Theta(n)$$ Is it correct to say $$n -1 \leq n \leq n +1 => f(n)=n=\Theta(n)$$ $$\sqrt{n}\leq|-2\sqrt{n}| = 2\sqrt{n}\leq3\sqrt{n} ...
0
votes
2answers
50 views

Monotone convergence of functions ant theor asymptotic power series

consider a sequence of functions $f_n:(0,\infty)\rightarrow\mathbb{R}$ which are positive and monotone, i.e. $$0< f_1\leq f_2\leq....\leq f_n\leq f_{n+1}...$$ Now let us assume we know the ...
2
votes
2answers
37 views

Help with recurrence $T(n) = T(n/2) + n$

I just need help seeing where I went wrong in this solution. $$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$ By master theorem, this is $\theta(n)$. However, when I try to solve it, it ...
1
vote
1answer
35 views

How can I prove $n - 2\sqrt{n} = \Theta(n)$

I want to prove the following $$n - 2\sqrt{n} = \Theta(n)$$ It's $n - 2\sqrt{n} \leq n = O(n)$ How can I prove the same for $\Omega(n)$
-4
votes
2answers
83 views

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$. [closed]

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$. What do i need to do here? Like step by step?
0
votes
1answer
22 views

Asymptotes and their like

Can an asymptote be a curve? From what I have read, it suggest that the numerator must strictly be only one degree higher than than the denominator. However mathematically speaking, a equation like ...
2
votes
1answer
47 views

Help me approximate this sum: $S = \sum_{j=2}^{N}{\frac{\ln \ln \ln \ j}{( \ln \ln \ j)^2}}$

I would like to figure out the asymptotic rate of growth for the sum $S = \sum_{j=2}^{N}{\frac{\ln \ln \ln j}{( \ln \ln j)^2}}$ in the limit of large $N$. Ultimately, I want to know if $S(N)$ is ...
3
votes
1answer
40 views

In which conditions $ f'(x)=O(g'(x))$ implies $f(x)=O(g(x))$?

First question, let $f,g:(-a,0)\rightarrow(0,\infty)$, introduce the notation: We say $f(x)=O(g(x))$ in $0$, if there exists constants $c,\epsilon>0$, such that $$f(x)\leq cg(x) \ \ \forall ...
2
votes
2answers
59 views

Show that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$

Show that $$\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$$ I've proven so far that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+O(\sqrt{x})$. I want to reduce this error ...
4
votes
2answers
168 views

Show that if $\int_0^x f(y)dy \sim Ax^\alpha$ then $f(x)\sim \alpha Ax^{\alpha -1}$

Let $f$ be a real, continuous function defined on $[0,\infty)$ such that $xf(x)$ is increasing for all sufficiently large values of $x$. Show that if $$\int_0^x f(y)\,dy \sim Ax^\alpha \quad ...
3
votes
1answer
77 views

Steepest descent method with movable maximum

Suppose we want to find the asymptotic behavior as $n \rightarrow \infty$ of the integral $$\int_C \frac{dz}{z} \frac{e^z}{z^n}=\int_C \frac{dz}{z} \exp(z-n \ln z)$$ where $C$ is some contour in the ...
3
votes
3answers
57 views

Bounding $\sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}}$

I'm looking for a bound depending on $N$ of $\displaystyle \sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}}$. The following holds $\displaystyle \sum_{k=1}^N \frac{1}{1-\frac{1}{2^k}} = \sum_{k=1}^N ...
1
vote
0answers
30 views

Power expansion with Big O notation regarding to logarithmic.

I want to know power series expansion calculation using Big O notation. That is $$1-{\displaystyle \frac{x\log^2 (x)}{(x+1)\log^2 (x+1)}}$$ at infinity. Someone calculate easily by using Big O ...
1
vote
1answer
24 views

converting asymptotic little-oh into big-oh

Let $f(n)$ be a random function such that $f(n)\cdot n^{1/4-\epsilon}\to 0$ for all $\epsilon>0$. Say we know that $f(n)\cdot n^{1/4}\not\to 0$. Does this imply that $f(n)=\tilde O(n^{-1/4})$? ...
6
votes
1answer
113 views

Asymptotics of $\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}$, is it $\frac{2}{\pi n}$?

I am trying to work out the asymptotics of $$\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}.$$ My numerical experiments suggest it might ...
1
vote
1answer
39 views

What is the limit of the below functions when n tends to inifinity?

What is the value for the functions in the image when limit n tends to infinity?. Also what is the asymptotic complexity (big $O$ notation) for all the four functions?. $$\begin{aligned}f_1(n) &= ...
0
votes
1answer
14 views

Big-Oh of $(\log_bn)^c$ is $O(n^d)$

I'm a CS freshman. In my discrete math textbook, it says ... whenever b > 1 and c and d are positive, we have $(\log_bn)^c$ is $O(n^d)$, but $n^d$ is not $O((\log_bn)^c)$ But why? Using ...
0
votes
2answers
41 views

Why does this inequality stand?

I stand that $\log n=O(n^{\epsilon})$ for any $\epsilon >0$. At a previous example we have shown that $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!}$$ where $d=\lfloor ...
2
votes
1answer
44 views

Show that $f(x) = O(1/x)$

Let $f:\mathbb{R}\to\mathbb{R}$ such that $f\ge 0$, monotonically decreasing and $\int_0^\infty f(x) \ dx < \infty$. Prove that $f(x) = O(1/x)$. So basically, both $f(x)$ and $1/x$ are ...
4
votes
1answer
67 views

How to use Laplace method to get the asymptotic expansion of multiple integral

I meet difficulty when I try to get the asymptotic behaviour of multiple integral as x tends to plus infinity. And $-1<$p$<1$ $$\int_x^{+\infty}\int_x^{+\infty}e^{-{\frac{1}{2\sigma^2(1-p^2)}\ \ ...
1
vote
2answers
68 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
6
votes
0answers
43 views

Comparing asymptotic forms of series

I've run into some asymptotic analysis in research here and there and largely it feels pretty magical to me. My research has led me to consider the following question which I haven't the slightest ...
1
vote
0answers
35 views

Hamming weight in multiple label

Assume you have a $N$ balls. You give each ball $T$ different labels randomly from $\{0,\dots, N-1\}$. So hamming weight of each of labelling varies from $0$ to $\lceil\log_2 N\rceil$. What is ...
5
votes
2answers
114 views

How to get the asymptotic form of this oscilatting integral?

So the integral is like this: $$\int_1^\infty \frac{\cos xt}{(x^2-1)\left[\left(\ln\left|\frac{1-x}{1+x}\right|\right)^2+\pi^2\right]}\mathrm{d}x$$ The question is how to get the asymptotic form of ...
0
votes
0answers
12 views

Finding the correct asymptotic functions

in an exercise of algorithms, I have to find a function $f(n)$ that is $Ω(n^2)$ and such that for every $n>0$ is $f(n)<n^2$. I also need to find a function $g(n)$ which is $Ω(n^2)$ but not ...
0
votes
1answer
40 views

What is the asymptotic behavior of the function counting the number of (not necessarily distinct) prime divisors?

From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition Ω(n), ω(n), νp(n) – prime power decomposition The ...
2
votes
1answer
23 views

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$.

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$. I believe this is false. Take $f(n) = 4n^2, g(n) = ...
3
votes
1answer
26 views

Find the asymptotic behavior of solutions of the equation

Find the asymptotic behavior of solutions $y$ of the equation $$x^5 + x^2y^2=y^6,$$ which tends to $0$ when $x$ tends to $0$. My solution: if $y=Ax^n$, then $$x^5 + A^2x^{2+2n}=A^6x^{6n}.$$ If ...
0
votes
2answers
48 views

How to prove order of equation using Big-Oh notation? [closed]

How can I prove this order equation using Big-Oh notation? $$O(3n^3+2n^2+5) = n^3$$
-1
votes
2answers
43 views

How to solve recurrence equation with logarithms using the Master Theorem

how do you solve this equation of recurrence? $T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$ The problem is the term $n*log_2(n)$. Can I only consider only $n$ as it's the larger then $log_(n)$ ...
2
votes
1answer
37 views

Finer asymptotic estimate of an integral

I'm studying the asymptotic behaviour for large $n\in \mathbb N$ of $\displaystyle \int_1^\infty \frac{1}{1+t^{n+1}}$ Using the substitution $u=(n+1)\ln(t)$, $$\displaystyle \int_1^\infty ...
9
votes
1answer
99 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
1
vote
1answer
24 views

Asymptotic Distribution of Quantiles

In order to prove that the sample $p$-percentile $x_p, p \in [0,1]$ from a sample of $n$ is asymptotically normally distributed as $n\to\infty$, it is necessary to show the following two limits. They ...
0
votes
1answer
51 views

Prove that $2^{n+1} = \Theta(2^n)$?

I need to prove that $2^{n+1} = \Theta(2^n)$? To do this, I need to show that there are positive constants $c_1,c_2$ such that $$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ ...for all sufficiently large ...
0
votes
1answer
43 views

Disprove $f(n) = 2^{2n}$ is $O(2^n)$

Disprove $f(n) = 2^{2n}$ is $O(2^n)$ Informally I know that this means we have to show that $2^{2n}$ grows much faster than $2^n$. More formally, I know that we need to show that for any $N$, ...
0
votes
3answers
58 views

Prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$

I need to prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$. I believe this statement is true, so I want to prove it. I know that $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such ...
0
votes
0answers
27 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
0
votes
1answer
47 views

Asymptotic sums and liminf

Given an arithmetic function $f(n)>0$ with $$\liminf \frac{g(n)}{f(n)}=C$$ for a certain constant $C$ and another function $g(n)>0$, in the study of the asymptotic bound for $$ \sum_{n\leq x} ...
0
votes
0answers
57 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
2
votes
1answer
32 views

Big O notation proof for a divided problem

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear ...
1
vote
2answers
51 views

How can I show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

I am preparing for an exam, and one of the problems on the study guide is: Show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$ If we declare n as some arbitrary number 5, then our summation would ...
4
votes
1answer
104 views

Is $\sum_{k\leqslant n} f'(k)f'(n-k) \asymp f'(n)f(n)$ when $f'$ is positive decreasing?

In this answer of a question of mine, the user Homegrown Tomato gave a nice argument that somewhat shows that $$\int_{\substack{t+s\leqslant x \\ t,s \geqslant 0}} f'(t)f'(s)dtds \asymp ...
1
vote
1answer
19 views

Order estimates

QUESTION: Suppose $y(x) = 3 + O (2x)$ and $g(x) = \cos(x) + O (x^3)$ for $x << 1$. Then, for $x << 1:$ (a) $y(x)g(x) = 3 + O (x^2)$ (b)$ y(x)g(x) = 3 + O (x^4)$ (c) $y(x)g(x) = 3 + O ...
2
votes
1answer
38 views

what is wrong with this proof? (proving the transitive property of Big O)

So the problem is if $f(n) \in O(g(n))$,and $g(n) \in O(h(n))$ then $f(n) \in O(h(n))$ Assume $f(n) \geq 0, g(n) \geq 0, h(n) \geq 0$ Proof: From assumptions, ...
1
vote
1answer
287 views

Limit involving tetration

Let the notation be $a^{\wedge\wedge}b = \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{b\,times}$ for tetration. My mentor conjectured the following: Let $n$ be a positive integer, then let $A(n)$ be ...
3
votes
1answer
41 views

Big O Notation and negative “n”

So I'm studying big $O$ notation right now and am working through a problem and got $O(x^{-10})$ and I'm just wondering if it's possible to even have a term with $O(x^{-n})$ because I've never come ...
2
votes
2answers
44 views

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$. I'm confused about how to taylor expand about u=1? How do I continue? Obviously first of all I have converted it ...
1
vote
2answers
27 views

does $f(n) \neq O(g(n))$ implies $g(n)=O(f(n))$ [duplicate]

Im pretty sure it doesn't, but how can I be sure? Was thinking by using $$f(x) = \sin(x) + 2$$ and $$g(x) = \cos(x) + 2$$ Thanks!`
0
votes
1answer
27 views

Big Theta of this modification of the secondary branch of the Lambert W function

I am looking to find the big-$\Theta$ of $-W_{-1}(-\frac{a}{n})$ in terms of elementary functions where $a$ is a constant. Looking around and I find that this should be $O(\log(n))$ and with maxima I ...