Hot answers tagged

2

Maybe I have misunderstood, but it seems to me that you are mixing up two different questions. The number of steps required to compute a sum of $n$ terms is $O(n)$. The final result of adding the numbers $1$ to $n$ is $\frac12n(n+1)$, which is $O(n^2)$.


2

This was the answer before OP had positivity conditions for $a_n$, $b_n$. Recall that the limit comparison test usually applied when the terms are positive. So, by making some negative terms, we might easily get a counterexample. Consider this, $$ a_n = (-1)^n + \frac1n $$ and $$ b_n= (-1)^n $$ Then $a_n/b_n = 1+(-1)^n / n \rightarrow 1$. However, $$ \...


1

Multiplication by a constant doesn't affect big-O fit. All polynomials of degree 3 are of the same order, so $10n^3 = O(0.42 n^3)$ is true.


1

I assume you meant $\log_2(n)$ and not $\log_2^n$. If I'm right, then take logarithms, say in base 2 (just for convenience). On the left you have $n$. On the right you have $\log_2(n)^2$. Now use L'Hospital's rule to compute $\lim_{n \to \infty} \frac{n}{\log_2(n)^2}$. From the result of this and the fact that $2^x$ is an increasing function, you conclude ...


1

The $\lfloor \sqrt{n} \rfloor$ factor in the summation is constant, so we can pull it out of the sum. Then we get $\lfloor \sqrt{n} \rfloor^3 \sum_{i=1}^k i^3$, where $k = \left\lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rfloor$. This is then a sum of cubes, for which there is the formula $\sum_{i=1}^k i^3 = \frac{1}{4} k^2 (k+1)^2$. As for the ...


1

Counter-example: $\frac1{(n+1) \ln(n+1)^2} \in ω(\frac1{n^{1+ε}})$ as $n \to \infty$, but $\sum_{n=1}^\infty \frac1{(n+1) \ln(n+1)^2}$ converges. The easiest way to prove it is that $\sum_{n=2}^\infty \frac1{(n+1) \ln(n+1)^2} \le \int_1^\infty \frac1{(x+1)\ln(x+1)^2}\ dx = [-\frac1{\ln(x+1)}]_1^\infty = \frac1{\ln(2)}$. We can extend this: $\sum_{n=2}^\...



Only top voted, non community-wiki answers of a minimum length are eligible