overall complexity of an algorithm

72 Views Asked by At

Is the following way of thinking correct?

Assume one has some Algorithm, which for some fixed integer $n$ and some $i = 1,\dots, k$ has computational complexity $O(i\times n^{2})$. Assume I have to run this algorithm $k$ times through all $i = 1,\dots, k$. Then, the overall complexity is $$ O(n^{2}+2n^{2}+\dots+k\times n^{2}) = O(\frac{1+k}{2}k\times n^{2}) = O(k^{2}\times n^{2}) $$

1

There are 1 best solutions below

0
On BEST ANSWER

That's right,

$$\sum_{i=1}^k T(i,n)\le\sum_{i=1}^k Cin^2=Cn^2\sum_{i=1}^k i=O(k^2n^2).$$

Technically you should specify $K,N$ above which the inequalities hold, but that will not influence the asymptotic result.