0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – greybeard Sep 13 '20 at 15:52
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.