An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in the order ofNote: This kind of question will be helpful in clearing Infosys recruitment.

The time complexity of building a heap with n elements is in the order of O(n).

Here's a step-by-step explanation:

1. A heap can be built by calling the heapify function for each element of the array, starting from the last internal node, and moving to the root node.

2. The heapify function, in the worst case, can take O(logn) time for a tree with n nodes (this is because the tree is a complete binary tree).

3. However, the time complexity for building a heap is not O(nlogn), even though we are calling the heapify function n times. This is because the height of the tree (and therefore the time complexity of the heapify function) is not logn for all elements.

4. Instead, we can calculate the time complexity as follows: for n elements, there are approximately n/2 leaves, n/4 nodes of height 1, n/8 nodes of height 2, etc. Therefore, the maximum number of nodes at height h is n/(2^(h+1)).

5. So, the total number of operations in heapify is the sum of the height of the nodes times the number of nodes at that height, which is approximately n/20 + n/41 + n/82 + n/163 + ... = n(0/2 + 1/4 + 2/8 + 3/16 + ...) = n.

6. Therefore, the time complexity of building a heap is O(n).