-1

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?

David Sherret
  • 109
  • 2
  • 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

1 Answers1

3

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)

Jim Wood
  • 154
  • 2