Complexity Analysis

Building the heap

As mentioned in the previous lesson, the time complexity of building a heap is O(N)O(N). This is not obvious right away so let’s analyse the algorithm.

The entire building of the heap can be expressed as NN heapify events. Each heapify event take O(h)O(h) time where hh is the height of the tree.

When I say heapify in this lesson, I mean the top to bottom heapify, the same can be proved for the bottom to up heapify as well.

Each heapify event can be provided with a tighter upper bound than hh. For example, for leaf nodes, the heapify event is just 11 operation since there is no node below to propagate the heapify to.

Number of operations

Step by step:

  • 1st1st element (root): hh levels below it, so hh operations
  • For the next two elements 2nd2nd to 3rd3rd: h1h-1 operations.
  • For the next four elements 4th4th to 7th7th: h2h-2 operations.
  • And so on…
  • Second last level: 2 operations.
  • Leaf nodes (last level): 1 operation.

For the sake of simplicity, let’s assume NN is a power of 22 so that we work with a complete binary heap.

Also, recall that the count of nodes at any level can be expressed in terms of NN. Nodes halves every level as two nodes connects to one node each time to go up a level.

  • Nodes in the last level (leafs) = N2\frac{N}{2}. Let’s call this level 00.

  • Nodes in the second last level i.e. level 11 = N4\frac{N}{4}.

  • Nodes in level 2 = N8\frac{N}{8}

  • And so on… where the last level, the level logNlogN has only 11 node, the root.

Compute time per level

List out the number of operations required for each level of the tree rather than each node because the count of operations will be the same for all nodes with the same level.

  • Level 00: 11 operation for N2\frac{N}{2} nodes.

  • Level 11: 22 operations for N4\frac{N}{4} nodes.

  • Level 22: 33 operations for N8\frac{N}{8} nodes.

  • Level logNlogN: logNlogN operations for 11 node.


T(N)=[1N2]+[2N4]+[3N8]+...+[(logN1)2]+[logN1]T(N) = [1 * \frac{N}{2}] + [2 * \frac{N}{4}] + [3 * \frac{N}{8}] + ... +[(logN-1)*2] +[logN*1]

T(N)=h=1logNhN2hT(N) =\sum_{h=1}^{logN} h *\frac{N}{2^{h}}

T(N)=Nh=1logNh12hT(N) =N*\sum_{h=1}^{logN} h *\frac{1}{2^{h}}

We can extend the summation to \infty to get the upper bound.

T(N)=Nh=1h12hT(N)=N*\sum_{h=1}^{\infty} h *\frac{1}{2^{h}}

The term can be derived from the sum of infinite GP.

Sum of infinite GP (x<1)(x<1) is:

n=0xn=11x\sum_{n=0}^{\infty}x^{n} = \frac{1}{1-x}

Differentiate both sides

n=0nxn1=1(1x)2\sum_{n=0}^{\infty}nx^{n-1} = \frac{1}{(1-x)^2}

Multiply by xx

n=0nxn=x(1x)2\sum_{n=0}^{\infty}nx^{n} = \frac{x}{(1-x)^2}

Putting x=12x = \frac{1}{2}, we get the second term.

n=0n2n=12(112)2=1214=2\sum_{n=0}^{\infty}\frac{n}{2^n} = \frac{\frac{1}{2}}{(1-\frac{1}{2})^2}=\frac{\frac{1}{2}}{\frac{1}{4}}=2

Putting this result back into the above equation


In the next lesson, we’ll see how to use the STL priority queue for heap operations.

Get hands-on with 1200+ tech skills courses.