Big Oh from function

Question

I'm having a lot of trouble finding big oh for the function:

$$f(i)=i+2i+\cdots+i\cdot i,$$

where $f(i)$ is the steps to run this function. Could you give me a hint as how to find it?

Much appreciated.

Answer 1

Hint: $$ f(n) = n+2n+\dots+n\cdot n = n\sum_{k=1}^n k = n\cdot\frac{n(n+1)}{2} $$

Answer 2

What you have is $f(i) = \sum_{j=1}^i ij = i\sum_{j=1}^i j = i\frac{i(i+1)}{2}$. This follows from the sum of the first $n$ natural numbers. Can you take it from here?

Answer 3

Your question is not precise. Big Oh question depends on whether you are looking for $i\to \infty$ or $i\to 0$. Since $f(i) = \frac 12 i^3 + \frac 12 i^2$,

[Case 1] $f(i) = O(i^3)$ as $i\to \infty$ since $\lim_{i\to \infty} \frac{f(i)}{i^3} = 1/2$.

[Case 2] $f(i) = O(i^2)$ as $i\to 0$ since $\lim_{i\to 0} \frac{f(i)}{i^2} = 1/2$.

Answer 4

Note that, you can write the function in a compact form as $$ f(i)=i+2i+\cdots+i\times = i( 1+2+\dots+i )= i \frac{i(i+1)}{2}. $$

Now, notice that

$$ \frac{i^2(i+1)}{2}\sim \frac{i^3}{2}, $$

as $i\to \infty$.