Given the following pseudo code, I'm wondering if my thought process is correct when trying to determine the time complexity.
for i = 0 to n-1
Add the numbers A[0] thru A[i].
Store the result in B[i].
The algorithm will loop n times, and since the last iteration will require the most amout of computations (n computations) the algorithm will in total make n^2 + f(n) computations. where f(n) is a polynomial of degree n^2 or less. Therefore this algorithm is quadratic O(n^2).
As the time complexity of Add the numbers A[0] thru A[i]. is \Theta(i), the time complexity of your code would be \Theta(1 + 2 + 3 + ... + \Theta(n)) = \Theta(n^2). Hence, your analysis for your code is true.
we can replace your code with the following code
for i 0 to n - 1
for j 0 to i
b[i] += a[j] <---
In order to find the big O of this algorithm we need to calculate how many times the 3rd row is executed.
just for simplicity lets say all a[i] elements equal to 1 so if we find the sum of b[i] when i is 0 to n -1 then we find the number of time the 3rd line was run.
i: b[i]
0: 1
1: 2
2: 3
..
n - 1: n
therefore the total sum of all B[i] is n * (n + 1) / 2 which is O(n^2)
B[i] = B[i-1]+a[i], no sane implementation would repeat the entire partial summation at each iteration. Your algorithm may beO(n^2)but prefix summation isn't.