Insertion Sort time complexity is O(n) in Best Case

[akash16]

Why Insertion Sort time complexity is O(n) in Best Case?

The best case for any sorting algorithm is when input is already in sorted order. Here in such scenario, the condition at while loop always returns false and hence it only iterates for the outer for loop, doing the job in linear time with O(n) time complexity.

void insertionSort(int*Arr, int len)
{
  for(int i=1; i<len; i++)
  {
    int j = i;
    int k = Arr[i];
    while(j > 0 && Arr[j-1] > k)
    {
      Arr[j] = Arr[j-1];
      j--;
    }
    Arr[j] = k;
  }
}