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

learn more… | top users | synonyms (1)

2
votes
0answers
23 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
1answer
22 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
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 ...
1
vote
2answers
31 views

Slow decreasing function that exhibits asymptotic behaviour.

I am currently doing some work on modelling the effects of treated nets usage on mosquito populations. Nets do not retain their maximum efficacy forever. They lose their chemical efficacy after about ...
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} ...
3
votes
1answer
52 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 ...
2
votes
2answers
35 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
34 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)$
-2
votes
2answers
65 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 ...
0
votes
1answer
38 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
42 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
39 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
47 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 ...
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
1answer
21 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 ...
1
vote
0answers
27 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 ...
6
votes
1answer
99 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
23 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})$? ...
4
votes
3answers
9k views

Family of functions with two horizontal asymptotes

I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch): Properties I'm looking for: ...
1
vote
1answer
38 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) &= ...
1
vote
0answers
70 views

Sums of Power Law random variables

Suppose $F$ is a Pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , \dots, X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
0
votes
1answer
11 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 ...
4
votes
1answer
55 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)}\ \ ...
9
votes
1answer
89 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 ...
5
votes
2answers
97 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 ...
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 ...
1
vote
2answers
45 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 ...
4
votes
1answer
100 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 ...
6
votes
0answers
39 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
33 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 ...
-1
votes
2answers
42 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)$ ...
0
votes
0answers
11 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 ...
3
votes
1answer
22 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 ...
2
votes
1answer
20 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) = ...
0
votes
2answers
43 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$$
5
votes
1answer
198 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
2
votes
1answer
34 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 ...
0
votes
1answer
45 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
42 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
0answers
24 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
46 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
50 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
31 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
48 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 ...
18
votes
6answers
1k views

Is there a slowest rate of divergence of a series?

$$f(n)=\sum_{i=1}^n\frac{1}{i}$$ diverges slower than $$g(n)=\sum_{i=1}^n\frac{1}{\sqrt{i}}$$ , by which I mean $\lim_{n\rightarrow \infty}(g(n)-f(n))=\infty$. Similarly, $\ln(n)$ diverges as fast as ...
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
36 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, ...
2
votes
1answer
102 views

Bound the probability of unlikely escape through one end of a thin rectangle

Consider the following elliptic PDE boundary value problem, \begin{eqnarray} & a u_x + b u_y + \frac{\alpha}{2} u_{xx} + \beta u_{xy} + \frac{\gamma}{2} u_{yy} = 0 \;, \quad {\rm ~for~} ...