# Comparing the efficiecy of 2 run times

I have a heap with $$n$$ elements. $$k$$ represent a number that is the height of one of the elements in the tree.

I need to compare two run times and prove what i claim.

The 2 run times are: $$(1)O(\lg n \cdot (\lg n - k))$$

And: $$(2)O(2^k \cdot \lg n)$$

Where: $$\lg n - k$$ Is a constant value.

For the first run time formula, its seems that we get: $$O(\lg n)$$

But how do i find the run time (and prove) for the second run time?

Thanks.

• Parts of this question could use interpretation guidance. a) in asymptotic resource requirement analysis, $n$ commonly is used to characterise problem size: How shall $\lg n - k$ Is a constant value be interpreted? b) run time [for a] second run time c) Comparing the efficiency of 2 run times – greybeard Sep 13 '20 at 15:52

In case of heap the worst case height could be $$O(\log n)$$.
$$O(2^k\cdot\log n) = O(2^{\log n} \cdot \log n) = O(n\log n)$$
$$\log(n)-k$$ is const $$\implies$$ $$2^{\log(n)-k}$$ is const $$\implies O(2^{k} \cdot \log(n)) = O(2^{\log(n)-k} \cdot 2^{k} \cdot \log(n)) = O(2^{\log(n)} \cdot \log(n)) = O(n \cdot \log(n))$$