I have some questions about Big-O notation:
1 Find the Big-O notation for the following sum: $1^2 + 2^2 + ... n^2$
2 Find the best (i.e., lowest) Big-O order for $f(n)$, where $f(n) = 1 + 4 + 7 + ...(3n+1)$. Hint: the possible answers are arranged in the increasing order of growth.)
- I have $O(n^3)$, $O(n^4)$, $O(n^6)$, $O(n^7)$ (these are the highest powers of $n$ the instructor has in the multiple choice question.)
I am totally lost on $2$. The choices are $O(1)$, $O(log(n))$, $O(n)$, $O(n^2)$, $O(n^3)$, $O(n^4)$.
Any help would be appreciated!
If $f(n)$ is an $n^{th}$ degree polynomial, then $f(n) = \mathcal{O}(n)$. If we can find polynomial expressions for those sums, then we can use this fact to find a big-O bound for them. For the first one, it is well-known that
$$\sum_{i=1}^{n} i^2 = 1^2 + 2^2 + ... n^2 = \frac{n(n+1)(2n+1)}{6}$$
For the second, if we consider it as an arithmetic series with $a_1 = 1$ and $a_n = 3(n-1) + 1$(note that I've reindexed the sequence - yours has $a_0 = 1, a_n = 3n + 1$), we can use the formula for arithmetic series $S_n = \frac{n(a_1 + a_n)}{2}$ to find a closed-form expression for the sum:
$$\sum_{i=0}^{n} (3i + 1) = 1 + 4 + 7 + ...(3n+1) = \frac{n(3(n-1)+2)}{2}$$
Do you see how to proceed from here?