Manipulating Equations with Big-oh

Note: first component is all context to inquiry classified "The Question" listed below:

Working via the CLRS Introduction to Algorithms , 3rd ed, in Chapter 6.4 as they are speaking about lots they mention:

Each phone call to MAX - HEAPIFY prices $O(lg\ n)$ and also BUILD - MAX - HEAP makes $O(n)$ such telephone calls.

Ok, I'm with them, the running time for for BUILD - MAX - HEAP is consequently $O(n\ lg\ n)$, they go onto say:

This upper bound, though proper, is not asyptotically limited.

I recognize this too due to the fact that actually MAX - HEAPIFY does not operate $lg\ n$ degrees each time it is called, yet instead it operates $h$ degrees where h is the elevation of the node it was gotten in touch with. So they mention:

Our tighter evaluation relies upon the buildings that an $n$ - component lot has elevation $\lfloor lg\ n \rfloor$ and also at the majority of $\lceil n/2^{h+1}\rceil$ nodes of any kind of elevation $h$.

Ok, with them still as I recognize the whole tree has dimension $n$ nodes which is actually making use of that formula when elevation = 0: $n/2^0 = n$.

The moment called for by MAX - HEAPIFY when gotten in touch with a node of elevation h is $O(h)$ therefore we can share the complete price of BUILD - MAX - HEAP as being bounded from above by:

$\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} \lceil {\frac{n}{2^{h+1}}} \rceil O(h) = O(n\displaystyle\sum_{h=1}^{\lceil lg\ n\rceil} {\frac{h}{2^{h}}})$

The inquiry

Here is where I'm shed, I do not get just how the $^{+1}$ went away on $2^{h+1}$. Is that some sort of word-of-mouth presumption that can be made when you position the formula within the Big - oh? Or due to the fact that they removed the ceiling function?

2022-06-07 14:39:19
Source Share
Answers: 1

$O(2^{n+1})=O(2\cdot 2^n)=O(2^n)$ given that for any kind of function $f(n)$ and also constant $C>0$ we have $O(C\cdot f(n))=O(f(n))$.

2022-06-07 15:06:32