# Finding the lower bounds of an algorithm

I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.

For eg, I have the following algorithm

For i=1, 2,...,n
For j=i+1, i+2,...,n
Add up array entries A[i] through A[j]
Store the result in B[i, j] Endfor
Endfor


How do I calculate the lower bounds of this algorithm

• Lower bound of what? Of the running time of your algorithm in terms of the length of the input? I guess you mean a non-trivial one. For the above example you can get easily a tight bound. Otherwise you try to bound everything from below as good as you can. – A.Schulz May 8 '13 at 7:50

## 1 Answer

Hint: The complexity is proportional to the number of reads from the array $A$.

• Asymptotically, that is. – Raphael May 8 '13 at 8:15