CODEWITHSUNDEEP
c++time-complexityheapheapsort
Avi
Avi

Reputation: 325

Why is the time complexity of creating a heap array not O(log(n!)) instead of O(nlogn)?

Insertion of a new element in a heap through an insert function "insert(A,n)" takes O(log n) time (where n is the number of elements in array 'A'). The insert function is given below:

void insert(int A[], int n)
{
   int temp,i=n;
   cout<<"Enter the element you want to insert";
   cin>>A[n];
   temp=A[n];
   while(i>0 && temp>A[(i-1)/2])
   {
      A[i]=A[(i-1)/2];
      i=(i-1)/2;
   }
   A[i]=temp;
}

The time complexity for the insert function is O(log n).

A function that will convert an array to a heap array is given as:

void create_heap()
{
   int A[50]={10,20,30,25,5,6,7};
   //I have not taken input in array A from user for simplicity.
   int i;
   for(i=1;i<7;i++)
   {
      insert(A,i);
   }
}

It was given that the time complexity of this function is O(nlogn).

-> But the insert function has a maximum 'i' of elements to compare in each call. I.e., the time complexity in a single run of the loop is O(log i) for each call.

-> So first it's log1, then log2, then log3 and so on till log6.

-> So for n elements of an array, the total time complexity would be log2 + log3 + log4 +....logn

-> This will be log(2x3x4x...xn) = log(n!)

So why is the time complexity not O(log(n!)) but O(nlogn) ??

Upvotes: 5

Views: 384

Answers (1)

Tony Tannous
Tony Tannous

Reputation: 14856

Log(n!) Is bounded by log(n^n) from log rules its n*logn

1*2*3*4*....*n = n!
n*n*n*n*....*n = n^n

Clearly n! < n^n

Then why use O(nlogn) when O(logn!) is a tighter bound? because nlogn is bounded by log(n!), surprising, is it not?

log(1*2*3*4*....*n) = log(1) + log(2) + ... + log(n)

Let's throw away first half 

log(1*2*3*4*....*n) > log(n/2) + log((n/2) + 1) + log((n/2)+2) + ... + log(n) 
                    > log(n/2) + log(n/2) + ... + log(n/2) 
                    = n/2*log(n/2) = O(nlogn)

enter image description here

Upvotes: 8

Related Questions