What will be the running time of the algorithm?

Question

Algorithms

According to my calculations, the number of iterations in the loop in the algorithm is equal to a number very similar to the Fibonacci number of the array length. If, for example, there is an array with 4 elements, the number of iterations in the loop will be: 0+1=1, 1+2=3, 3+3=6, where in all expressions the first term is the number of iterations at the moment, and the second is the index from 1 to (array length)-1. I don't know if there is a name for such a read, but my question is: how to express the running time of this algorithm in O-big? Also, later I calculated that the number of iterations is approximately equal to (length of the array squared) / 2, is it possible to write in this way that the running time of the algorithm is O (N ^ 2 / 2)?

Answer 1

Checking on small numbers does not always work. there are fibonacci, a square and the devil knows what they look like.
If you have something like for "i=1...n do for j = i..n do" or some other 2 nested loops, where the internal variable runs from or to the external variable, then the exact number of iterations will be n(n+1)/2, which is O(N^2).
Your last judgment is correct.