trouble writing this code with complexity O(N)

Question

Task:

given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

My code:

def search(A):
   j=1
   while j in A:
      j+=1;
   return j;

Why is my time complexity O(N^2)?

Is not *O(n^2)* is *O(k*N)* where k is the lowest integer that does not occur in A — Dani Mesejo, Jan 11 '19 at 00:16
`1 if min(A) > 1 else (max(A) + 1 if max(A) > 0 else 1)` returns the same thing. It returns 1 when all numbers are non-positive. — GeeTransit, Jan 11 '19 at 00:18
@roganjosh I dont think that is write for example `[4, 5]` the answer is 1 not 3 — Dani Mesejo, Jan 11 '19 at 00:18
@DanielMesejo yep, I threw a suggestion out off the top of my head and you correctly shot it down in less than a minute :P But it's closer, I guess, and hopefully gives the OP a different angle — roganjosh, Jan 11 '19 at 00:20
What is the reasoning behind the claimed time complexity? Does that claim include some external code? — user2864740, Jan 11 '19 at 00:23
@DanielMesejo actually, my first pass wasn't that far off, You only have to make a small mod to find the amount to subtract but I leave that to the OP — roganjosh, Jan 11 '19 at 00:23
There is not really enough info to say what the complexity is unless you know what `A` is passed in (this would be an OK implementation if A was a set or a dict). I assume it's a dumb coding challenge that calls Python lists "arrays". — wim, Jan 11 '19 at 00:25
@DanielMesejo yes true so when I run it on a case where the answer is N then it gives me N^2 — mobelahcen, Jan 11 '19 at 00:25
It is `O(N)` in the best case and `O(N^2)` in the worst. I guess a constant `O(N)` algorithm is expected. — Selcuk, Jan 11 '19 at 00:27

AndreasT · Answer 1 · 2019-01-11T00:46:04.633

1

You are doing an O(N) walk over potentially all the items in the list that are positive. In every iteration you let python make another O(N) walk of the list, by asking 'j in A'? which runs through potentially all elements of A, searching for j. So your complexity becomes: O(N) * O(N) = O(N^2)

edited Jan 11 '19 at 00:46

answered Jan 11 '19 at 00:39

AndreasT

9,417
11
46
60

Perfect answer. – celicoo Jan 11 '19 at 00:55

Daniel Soutar · Answer 2 · 2019-01-11T00:56:21.437

0

Suppose your input is of the form 1..N.

Then your code will perform N iterations, each of which it potentially checks the entire length of the list to see whether the current value of j is in the list. N iterations of checking the entire list of length N gives N * N = N^2.

This is a worst-case example, but we don't know what the typical input is supposed to be. Maybe you know it, maybe you don't. A simple and worst-case-optimal way of doing this would be to sort the list and then find the first 'gap' between items in your list. Something like this:

def my_search(A):
   A = [i for i in sorted(A) if i > 0]  # Gets rid of <1 values as well
   min_pos_val = 1
   for val in A:
      if val > min_pos_val:
         return min_pos_val
      min_pos_val += 1
   return min_pos_val

edited Jan 11 '19 at 00:56

answered Jan 11 '19 at 00:27

Daniel Soutar

827
1
10
24

The solution was not asked for. Also your solution is O(N logN) because of the sort. – AndreasT Jan 11 '19 at 01:01
You're right on both counts, but on the latter I didn't say that the proposed solution was O(N^2). – Daniel Soutar Jan 11 '19 at 01:03

Demi-Lune · Answer 3 · 2019-01-16T13:37:49.760

-1

The "in" operator is O(N). And the "while" is O(the returned value).

[edit] Let me detail this: your code is equivalent to

j = 1
while True:     # is O(the returned j)
   if j in A:   # is O(N), bec. has to go through the whole array
      j += 1
   else: 
      return j

So in a worst case, your algo is indeed O(N^2). In best cases (e.g. if 1 not in A) the algo is only O(N).

If A is a set (not a list nor array.array), it'll be O(N) on average. See details here: https://wiki.python.org/moin/TimeComplexity or Complexity of *in* operator in Python.

edited Jan 16 '19 at 13:37

answered Jan 11 '19 at 00:18

Demi-Lune

1,868
2
15
26

5

I don't actually know what you're trying to convey here – roganjosh Jan 11 '19 at 00:20
@user2864740 There is no `in` in the `while` syntax. I think you're talking about the `for` loop. – GeeTransit Jan 11 '19 at 00:22
1

@GeeTransit `while j in A:` – roganjosh Jan 11 '19 at 00:32
What I meant is that your example is interesting in the sense that at first glance, the "while" seems to be the only loop, hence you think it is O(N). However, "j in A" is also hiding another loop (which is also O(N)) – Demi-Lune Jan 11 '19 at 09:08
The other point, already mentioned by Daniel, is that in a worst case scenario your code is O(N^2) ; for example if A=range(1000). But in other cases (e.g. A=range(2,1002) which is a best-case scenario) your code will be O(N). – Demi-Lune Jan 11 '19 at 09:12

trouble writing this code with complexity O(N)

3 Answers3