ACE Test Series

Question

why TC is nlogn?

Comments

I think it's so because the outer loop will still run $n$ times while the inner loop which is used to find the correct position to enter the element in, will take $log(n)$ time, making it $O(nlogn)$ in the worst case.

 

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1; 
       /* Move elements of arr[0..i-1], that are 
         greater than key, to one position ahead 
         of their current position */
       while (j >= 0 && arr[j] > key)
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       }
       arr[j+1] = key; 
   } 
} 

---

for 2nd element you just need one comparison log(1) +1 comparison

for 3rd element you need log(2)+1 comparison

for 4th element you need log(3)+1 comparison

for 9th element you need log(8) + 1 so 4 comparison around

so overall for upper bound log(1)+log(2)+log(3)+log(4)+.....+log(n-1) + (n-1) < nlogn +(n-1)

for lower bound = log(1)+log(2)+log(3)+log(4)+.....+log(n-1) + (n-1) > log(n/2)+ .....log(n-1)+(n-1)

                                                                                                                    > n/2log(n/2)+(n-1)

Now looking at upper bound and lower bound I can say its $\Theta$(nlogn)

---

For inner loop, using binary search we can reach to elements correct position in $\Theta$(log n) time, but to rearrange elements by swapping complexity will still be $\Theta$(n) . Hence overall complexity will remain same $\Theta$($n^2$).

---

overall time complexity will remain same but notice that they are asking about number of comparisons only ...that will reduce!