I need a little help with a problem. I just started reading about O-notation but I'm still new when it comes to analysing code.
So here's the problem:
The following pseudocode is given, where A is a number field whose elements over the indices 1 to length(A) can be accessed
1: procedure Adder(A)
2: for i <- 1 to length(A)
3: for j <- length(A) to 1 do
4: if i ≠ j then
5: A[i] <- A[i] + A[j]
Give the complexity of the following lines of code in big-O notation:
So for lines 4-5 I thought it should be simply O(1) since it simply just adds 2 elements.
With the other two I'm really unsure.
For line 3-5 I think it should be O(n) where n is the number of indices in the number field.
And finally for lines 2-5 I would say it's O(n^2) since we now have to loops?
That seems correct to me, although you may want to reformulate some of the justification you have
lines 4-5 I thought it should be simply O(1) since it simply just adds 2 elements.
It is O(1) because no matter what the input is, the algorithm will end up doing either 1 or 2 instructions. It will never grow bigger than 1 or 2
finally for lines 2-5 I would say it's O(n^2) since we now have to loops?
It is O(n^2) because the nested loops are iterating on the sequence you have as input. No matter what happens, if the input is of length N, you will have to make N loops, and N loops inside. So you end up with N * N which is N^2 as you suggested.