0

I've got a problem where I need to add items to a list. It has to use stdin, and be in Θ(n). I only seem to be able to get it in Θ(n^2). This is my code:

for i in range(int(r1)): # size of list being made
    for line in sys.stdin.readline().strip().split(" "):
        a.append(line)
Input:  Output: [1, 2, 3]
1
2
3

As far as I'm aware that's in Θ(n^2). I have tried doing this:

for i in range(int(r1)): # size of list being made
    a.append(sys.stdin.readline().strip().split(" "))
Input:  Output: [[1], [2], [3]]
1
2
3

Because the elements of the second attempt are in their own sub-lists then they don't work for the rest of my program. Any adivce?

GuardGoose
  • 57
  • 7
  • Uhhm, why do you believe that append is O(n^2)? The amortized average case and the worst case for an append operation are both O(1). You might see worse performance if you were inserting, but appends are blazingly fast. – g.d.d.c Feb 22 '19 at 16:38
  • I don't think your big O notation is correct. Just because it's a list doesn't make it squared, since you expect the list to have 1 member each time. – Rocky Li Feb 22 '19 at 16:39
  • I was more meaning for the loops that cause the complexity to increase? – GuardGoose Feb 22 '19 at 16:41
  • That's only a concern if you're iterating over the _same_ list repeatedly. If you have to read input three times (like you're doing) then you're doing something in constant time that's necessary for your algorithm. – g.d.d.c Feb 22 '19 at 16:43

2 Answers2

1

Have you tried using extend instead of append?

a.extend(sys.stdin.readline().strip().split(" "))

An explanation is in this question

You can also check this cheat sheet for complexity notation

nickyfot
  • 1,932
  • 17
  • 25
1

This is not in Θ(n) nor is it in Θ(n^2). The complexity depends on many number of different variables: size of list being made, and number of spaces on each line of stdin. The outer for loop executes list-size number of times; body of that loop executes number-of-spaces-on-each-line number of times. So your complexity is more like Θ(r * k_i) for all i in [0, r] where k_i is the number of spaces of the i'th stdin.

miara
  • 847
  • 1
  • 6
  • 12