1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – A.Schulz
    May 8, 2013 at 7:50

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Asymptotically, that is. $\endgroup$
    – Raphael
    May 8, 2013 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.