CODEWITHSUNDEEP
python-3.xalgorithmtime-complexitypseudocode
Karl Karlsson
Karl Karlsson

Reputation: 125

Finding a more effective algorithm

I have the following pseudocode:

for i = 0 to n-1
    Add the numbers A[0] thru A[i].
    Store the result in B[i].

The worst case time complexity of this must be O(n) since assigning a new element to B is just O(1) and the code runs the for loop n times. Is that correct?

My task is to find a more effective algorithm than the one above. I mean O(n) is already pretty fast so i don't know how I would find a more effective algorithm. Does anyone have any ideas?

Thanks in advance!

Upvotes: 0

Views: 77

Answers (2)

Óscar López
Óscar López

Reputation: 236094

If you have to add all the numbers from A[0] to A[i] in each iteration, then it's O(n^2) complexity. For example, in Python:

# O(n^2) solution

a = [2, 3, 5, 7, 1, 9, 8]
b = []

for i in range(len(a)):
    sum = 0
    for j in range(i+1):
        sum += a[j]
    b.append(sum)

What you can do to make this O(n) is to calculate the current sum using the previous results, like this:

# O(n) solution

a = [2, 3, 5, 7, 1, 9, 8]
b = [a[0]]

for i in range(1, len(a)):
    sum = b[i-1] + a[i]
    b.append(sum)

The result will be the same in both cases, but the second version will have O(n) complexity:

b
=> [2, 5, 10, 17, 18, 27, 35]

Upvotes: 4

Vüsal
Vüsal

Reputation: 2706

The O(n) algorithm for this would be something like: 

sum = 0
for i = 0 to n-1
    Add A[i] to the sum
    Store the sum in B[i].

There is no way to find an algorithm for this problem with the runtime complexity less than O(n) because you NEED to visit all the items in array in order to calculate the sum of all of them. This statement applies to a case when you don't have any preliminary knowledge about the array structure.

Upvotes: 3

Related Questions