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

learn more… | top users | synonyms (1)

7
votes
3answers
174 views

Asymptotic behavior of the first step in a best strategy

Consider the game described here, but for a sequence $X_1,\ldots,X_n$ of i.i.d. uniform rv's on $\lbrace 1,\ldots,n \rbrace$ (in the original game $n=6$). Using the original notation, let $a_n$ denote ...
6
votes
4answers
872 views

Big $\mathcal{O}$ Notation question while estimating $\sum \frac{\log n}{n}$

I have a function $S(x)$ which is bounded above and below as follows: $f(x) + C_1 + \mathcal{O}(g(x)) < S(x) < f(x) + C_2 + \mathcal{O}(g(x))$ as $x \rightarrow \infty$ Can I conclude that ...
5
votes
2answers
491 views

Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$ - Part II

This is a follow up of Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$ More details can be found in the above thread. Let $S(n) = \displaystyle ...
4
votes
3answers
1k views

Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq ...
2
votes
1answer
276 views

Max of functions are in big O of the sum of their individual big Os

$\max(f(n), g(n)) = O(f(n) + g(n))$ How do I prove this? Also I'd appreciate the markup being corrected, thanks.
8
votes
3answers
231 views

Is it legitimate to write nested big-Os in an asymptotic formula for a multivariable function?

Suppose I have a 2-variable function $g(k,n)$ and I know that $g(k,n)=O(n^{f(k)})$, for fixed $k$ as $n \rightarrow \infty$, for some function $f=f(k)$. Suppose I also know that $f(k)=O(\log k)$. ...
2
votes
1answer
430 views

Problem calculating theta notation

Hello i have to solve the following problem find an $\displaystyle f(k)$ where $\displaystyle S_k=\theta(f(k))$ where $\displaystyle S_k =\sum_{n=1}^{k^2-1} \sqrt{n}$ I tried first of all to ...
5
votes
2answers
172 views

function asymptotic where $f(x) = \frac{a + O(\frac{1}{\sqrt{x}})}{b + O(\frac{1}{\sqrt{x}})}$

If $a$ and $b$ are positive real numbers, and if $f(x)$ has the following asymptotic property $f(x) = \frac{a + O(\frac{1}{\sqrt{x}})}{b + O(\frac{1}{\sqrt{x}})}$ then is the following true? $f(x) ...
2
votes
2answers
1k views

How can I determine asymptotic growth of binomial coefficients?

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$? Is there a general ...
10
votes
2answers
315 views

Positive integers $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}} > 1$ satisfying $\sum_{i = 1}^{n} p_{i}^{-r_{i}} < 1$

A divisor $d$ of $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}}$ is unitary if and only if $d = p_{1}^{\varepsilon_{1}} \cdots p_{n}^{\varepsilon_{n}}$, where each exponent $\varepsilon_{i}$ is either $0$ or ...
7
votes
3answers
261 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...
2
votes
0answers
174 views

Upper bound for the quality of an $abc$-triple

A triple of positive integers $(a,b,c)$ is an $abc$-triple if $a$ and $b$ are coprime and $c = a + b$. Define the quality or power of an $abc$-triple as $P(a,b,c) = \frac{\log c}{\log ...
10
votes
5answers
580 views

Bounding the integral $\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}}$

If $x \geq 2$, then how do we prove that $$\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}} = O\Bigl(\frac{x}{\log^{n}{x}}\Bigr)?$$
3
votes
2answers
204 views

Sharp upper bounds for sums of the form $\sum_{p \mid k} \frac{1}{p+1}$

Are there known sharp upper bounds for sums of the form $\sum_{p \mid k} \frac{1}{p+1}$ for $k > 1$ subject to the constraint $\sum_{p \mid k} \frac{1}{p+1} < 1$? (The factor of +1 in the ...
6
votes
3answers
589 views

Numerically estimate the limit of a function

Is there an algorithm that will allow me to numerically compute the limit of a function f(x) in a principled way? The most naive algorithm would be to continue to compute the function for larger ...
0
votes
3answers
365 views

Why do some limits “explode” to infinity?

For example: the limit of $e^t$ as $t$ approaches infinity is simply infinity. but the limit of $e^{t^2}$ cannot be found because it explodes? Is this due to the fact that there are differing types ...
4
votes
3answers
550 views

Formally proving that a function is $O(x^n)$

Say I have a function $f(x) = ax^3 + bx^2 + cx + d$ where $a > 0$. It's clear that for a high enough value of $x$, the $x^3$ term will dominate and I can say $f(x) \in O(x^3)$, but this doesn't seem ...
2
votes
1answer
306 views

Limit of the sequence $nx_{n}$ where $x_{n+1} = \log (1 +x_{n})$

Suppose $x_{1}>0$, and consider the sequence, $\{x_{n}\}$ defined as follows: $$x_{n+1}=\log(1+x_{n}) \quad n\geq 1 $$ Find the value of $\displaystyle \lim_{n \to \infty} nx_{n}$ I am having trouble ...
12
votes
3answers
394 views

A recurrence that wiggles?

Consider the following sequence $a_n$: $a_1 = 0$ $a_n = 1 + \frac{1}{2^n-2} \sum_{i=1}^{n-1} \binom{n}{i} a_i$ The first few terms are $0,1,\frac{3}{2},\frac{13}{7},\frac{15}{7}$. The sequence ...
0
votes
1answer
122 views

Big O boundary condition truth value

Note: logs below are base 2. (Not sure how to do subscripts here) Wondering if the below equation is true when thinking asymptotically (Computer Science) $log_2((n!)^n) = O(n \sin(n \frac{\pi}{2}) ...
2
votes
2answers
549 views

Big O comparison in asymptotic cases

I'm trying to find out if this is a true statement. Assuming asymptotic cases $n \sin(n \frac{\pi}{2}) + \log{n} = O(3)$ How would you go about solving a problem like this systematically? Note: O ...
4
votes
1answer
1k views

Determinant of a polynomial matrix

A matrix determinant (naively) can be computed in $O(n!)$ steps, or with a proper LU decomposition $O(n^3)$ steps. This assumes that all the matrix elements are constant. If, however the matrix ...
5
votes
6answers
850 views

Which one is bigger $2^{n!}$ or $(2^{n})!$

Which one is bigger $2^{n!}$ or $(2^{n})!$? where n∈N.
4
votes
3answers
6k 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: ...
20
votes
3answers
3k views

Prove that this function is bounded

This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone ...