0

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] = ans[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 explanations 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?

luma
  • 79
  • 1
  • 7
tori
  • 3
  • 2

2 Answers2

0

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).

Berthur
  • 4,300
  • 2
  • 14
  • 28
  • I see! So is it like calculating the memory location of each element directly instead of getting it by traversing the array from the beginning? – tori May 26 '22 at 22:17
  • @tori Exactly. It is how computers do it in practice. Essentially (somewhat simplified): Arrays are stored in RAM memory and each slot has a memory address. A program that knows the address can read the memory at that address in constant time, regardless of how much RAM you have. – Berthur May 27 '22 at 09:14
0

time complexity

Big-O cheat sheet

luma
  • 79
  • 1
  • 7