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?

  • 1
    @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
  • 1
    @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
  • 1
    @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)

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.