Forgive me if this should be in StackOverflow or Mathematics instead!

I was given the following question at an interview:

`Given an array of unique integers, find the first missing non-negative integer that is missing to form a consequence sequence of non-negative integers. For example, the input [3, 4, -1, 0, 1] should give 2. The input [1, -3, 2, 0] should give -1 (i.e no missing numbers). The input of [-2, -3, -5] should give 0 `

I came up with a solution that is something akin to here: https://play.golang.org/p/b2pXr9kZYxM:

`func findMissingNumber(nums []int) int{ j := 0 for i, num := range nums { if num < 0 { nums[i], nums[j] = nums[j], nums[i] j++ } } if j >= len(nums) { return 0 } count := 0 for i:=j ;i < len(nums);{ count++ if nums[i] == i-j { i++ continue } if nums[i]+j >= len(nums) || nums[nums[i]+j]+j >= len(nums) { nums[i] = -1 i++ continue } temp := nums[nums[i]+j] nums[nums[i]+j]= nums[i] nums[i] = temp } fmt.Println(count) for i := j; i < len(nums); i++ { if nums[i] == -1 { return i - j } } return -1 } `

Both the interviewer and I agreed that my solution could’ve been slightly more optimized (GeekForGeek seems to agree) but we were unsure if the worst-case for my solution was $ O(N)$ or $ O(N^2)$ .

It seems like my solution has $ $ O(N) + O(N/2) + O(N/4) + O(N/6) +\cdots+ O(1) $ $ which becomes essentially: $ $ \frac{N}{2}\sum_{n=1}^{N} n^{-1}$ $

My calculus is a bit rusty (as are my algorithm skills) but I know this is a series diverges for $ N \to \infty$ . But can I say that for N sufficiently smaller than infinite (i.e Integer.Max), my worst-case becomes simply $ $ O(kN) = O(N)?$ $