Comparing the efficiecy of 2 run times

Question

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.

Answer 1

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)$

Answer 2

$\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))$