I sometimes get confused with the time complexity analysis for the code that includes arrays. For example:
ans = [0] * n
for x in range(1, n):
ans[x] = and[x-1] 1
I thought the for-loop had a time complexity of O(n^2) because it accesses elements in the array with n elements, and it repeats the same thing for n times.
However, I've seen some explanation saying it takes just O(n); thus, my question is: when we analyze the time complexity of a program that accesses elements in an array (not necessarily the first or the last element), should we include the time to access those array elements, or is it often ignored?
CodePudding user response：
Indexed access is usually a constant-time operation, due to the availability of random access memory in most practical cases. If you were to run this e.g. in Python and measure the time it takes for different values of n, you will find that this is the case.
Therefore, your code only performs one loop from 1 to n and all other operations are constant-time, so you get a time complexity of O(n).
Your thinking is otherwise right - if this was a linked list and you had to iterate through it to find your value, then it would be O(n2).
CodePudding user response：