2

I'm wondering what's the Big O running time of the below simple program:

dates = [0,2,3,4]
sample_list = [1,2,3,4]
for i in range(0, 4):
    sub_list = sample_list[i+1:]
    if dates[i] in sub_list:
        count += 1

Is the running time O(n) or O(n**2)? I know the running time is at lease O(n) because I have a for loop, but how about the if dates[i] in sub_list statement? What's the running time for that?

Alan Kavanagh
  • 9,425
  • 7
  • 41
  • 65
vivi11130704
  • 431
  • 8
  • 21
  • 1
    `O(n)` or `O(n**2)` is meaningless without a definition for `n`... What is `n`? the number of elements in `dates`, in `sample_list`, in both? The number of lists?... – Julien Nov 06 '17 at 01:14

1 Answers1

3

Your loop does not seem to depend on the length of your list(s), even though it probably should. However, the call to sample_list[i+1:] will depend on the size of sample_list as well as dates[i] in sub_list.

For this reason, your code is O(n) where n is the length is sample_list.

Jacob G.
  • 28,856
  • 5
  • 62
  • 116
  • So what if I change it into `for i in range(0, len(dates))` ? Does that give me O(n)? – vivi11130704 Nov 06 '17 at 01:03
  • As Stefan pointed out, it's already `O(n)`, but it would be better to not hardcode the indices. – Jacob G. Nov 06 '17 at 01:05
  • I see. So if I'm understanding it correctly, `if dates[i] in sub_list` doesn't increase the running time to O(n^2). However I was reading this post: https://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python and it seems like an "in" operator in a list has O(n) running time. Since I'm wrapping a for loop outside this in operator. Shouldn't it be O(n^2) for my case? – vivi11130704 Nov 06 '17 at 01:12
  • It would be `O(n * m)` where `n` is the length of `sample_list` and `m` is the length of `dates` if you used `len(dates)` instead of `4` in your for-loop. – Jacob G. Nov 06 '17 at 01:13
  • I see what you say. Interesting. Thank you! – vivi11130704 Nov 06 '17 at 01:15
  • @vivi11130704 If you don't have any other questions, feel free to accept my answer :) – Jacob G. Nov 06 '17 at 01:30