I need help with time complexity in c++

#include <iostream>
using namespace std;
 
int binarySearch(int a[], int item, int low, int high) //we use binary search to find location of where the
{                                                     //the selected element in insertion sort should be inserted 
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (item == a[mid])
            return mid + 1;
         else if (item > a[mid])     
            low = mid + 1;
        
        else
        high = mid - 1;
    }
 
    return low;
}
 

int insertionSort(int a[], int n)
{
    int i, loc, j, selected;
 
    for (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
    return 0;
}
 

int main()
{
  int size;
  scanf("%d",&size);
  int arr[size];
  for (int i=0;i<size;i++){
      scanf ("%d",&arr[i]);
  }
  
  insertionSort(arr, size);
 for (int i=0;i<size;i++){
     printf("%d  ",arr[i]);
 }
    return 0;
//Done with the help of this website https://www.geeksforgeeks.org/insertion-sort/    
}

This is the code for binary insertion sort but I can’t seem to figure out how to reduce it’s time complexity

أضف اجابة

أضف اجابة

‫تصفح