# Big O of loop of 0…n with nested loop doing k iterations [duplicate]

My coworkers and I are discussing this code and need a third party to settle our discussion :)

``````Random randNum = new Random();
int[] A = Enumerable.Repeat(0, 1000).Select(i => randNum.Next(0, 100)).ToArray();
int k = randNum.Next(0, A.Length);
int[] B = new int[A.Length - k];

for (int i = 0; i < B.Length; i++)
{
int min = A[i];

for (int j = i + 1; j <= i + k; j++)
{
min = Math.Min(A[j], min);
}

B[i] = min;
}
``````

What would this be considered in big O notation?

## marked as duplicate by Bart van Ingen Schenau, MetaFight, Ixrec, user22815, gnatJan 20 '16 at 6:58

• @gnat you could say that for any big o question. I'm asking for this situation. – David Sherret Jan 19 '16 at 20:40
• Just to be sure I'm reading this correctly is A.Length = 1000 in this code? – Jim Wood Jan 19 '16 at 20:46
• @JimWood yes, that's right – David Sherret Jan 19 '16 at 20:47
• @DavidSherret I'm sorry, what's not clear here? The runtime is constant-bound since there is no input. If you implicitly assume that the "input" is the size of `A`, then you can trivially calculate it, since the runtime of the inner loop depends on `k` only, and you never write to it after the initialization. – Ordous Jan 19 '16 at 20:49
• @DavidSherret I think gnat's point is, beyond defining what Big-O notation is, this question has little to no value for the community as a whole. And, as noted by gnat, the definition part of this question has already been asked and answered. – MetaFight Jan 19 '16 at 21:42

Let's assume that you want Big-O in terms of the size of the array A (ie `n = A.Length`).
The size of B is `A.Length-k`, and `k` is some random number between 0 and the size of A.
Big-O is all about worst-case scenarios. I'll leave it as an exercise to the reader to prove the worst-case here is when `k = A.Length / 2 = n / 2`. In such a case, `B.Length = A.Length - k = n / 2`.
Then we have both loops doing `n / 2` work, for a final answer of O(n^2)