What is the running time of Insertion Sort when the input is an array that has already been sorted?

\Theta(n)
  • \Theta(n^2)
  • \Theta(\log n)
  • \Theta(n \log n)

Each test in the inner for loop will fail because the value at position i is never less than the value at position i-1.