Show running time of algorithm on input of size $n$ is $\Omega (f(n))$

Question

Basically I'm given this algorithm where I have an array $A$ of integers which outputs an $n \times n$ array $B$ where $B[i,j]$ contains the sum of the array entries $A$ and asked to give a bound of the form $O(f(n))$ on the running time of this algorithm on an input of size $n$, which I found to be $O(n^{3})$. How can I show that the running time of this algorithm is also $\Omega(f(n))$?

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

Answer 1

It looks like you can improve that runtime-complexity to $O(n^2)$. Note that $B[i,j] = B[i,j-1] + A[j]$. Because of this, you don't have to sum up the entries $A[i]$ through $A[j]$ (which is $O(n)$) but you just need to make sure that $B[i, j-1]$ is defined, if it is not defined just let it be zero, and then take $B[i,j] = B[i,j-1] + A[j]$ (which is constant time).

As for showing that the algorithm is $\Omega(n^2)$, I suppose you could just state that in order for the algorithm to complete we unavoidably have to fill in half of an $n \times n$ matrix. This means that the algorithm has to perform at least $\frac{1}{2}n^2$ operations, so it is $\Omega(n^2)$.

For i in 1..n
  For j in i+1..n
    If (j == i+1)
      B[i,j] = A[j]
    Else
      B[i,j] = A[j] + B[i,j-1]
  EndFor
EndFor

Note that $B[i,j]$ is undefined if $j = i+1$.