Complexity for array iteration that is constantly reduced

Question

So I'm a bit unsure what to really call this time complexity (I think it's O(N^2), but I'm not sure if I can call it that )

void solve(int[] nums, int k){
 int len = nums.length; 
  while(len > 0){ 
   for(int i = 0; i < len; i++){ System.out.println("hello"); }
   len-=k;
  }
}

So I realize that it's: n + n-k + n-2k + n-3k + ... I know I'm not halving the search space in each iteration so it's obviously not n*log(n) where n is the size of the array. I do realize that it's similar to divergent series (1+2+3+4+...); hence, my earlier assumption of this being O(N^2) == n(n+1)/2, but can I really call it that? Thanks.

Answer 1

Intuitively, we should expect this to be something like Θ(n² / k + n). If you imagine each unit of work as a square, you can imagine that we're building a triangle out of those squares. Each column represents one iteration of the outer loop. The height of the triangle is n, the width of the triangle is (n / k), and so we'd expect something like this to come out. For example, if k = 1 and n = 5, the triangle looks like this:

*
**
***
****
*****

If k = 2 and n = 6, the triangle looks like this:

*
*
**
**
***
***

That n term in there is necessary because if we allow k to get really, really large, we still always do at least one iteration of the loop, and so we don't want our runtime to drop to zero.

Now, let's see whether the math agrees with us. As you mentioned, you're looking at the sum

n + (n - k) + (n - 2k) + (n - 3k) + ... + (n - (n/k)k).

There are a total of (n / k) + 1 copies of n term here, so we can regroup things as

n((n / k) + 1) - (k + 2k + 3k + ... + (n/k)k).

We can then factor out a k term to get

n((n / k) + 1) - k(1 + 2 + 3 + ... + (n / k)).

That second term is Gauss's famous sum stopping at (n / k), which works out to

n((n / k) + 1) - (n / k)((n / k) + 1) / 2.

Factoring out an ((n / k) + 1) term gives us

((n / k) + 1)(n - n / 2k)

If we now multiply everything together, we get

n(n / k) - n² / 2k² + n - n / 2k

= 2n²k / 2k² - n² / 2k² + n - n / 2k

= (2n²k - n²) / (2k²) + n - n / 2k

= Θ(n² / k + n).

So the math checks out with our intuition.