# What kind of growth is $O(0.24\cdot K\cdot 2^w)$

I've calculated the running time of an algorithm I'm interested in to be

$$O(0.24\cdot K\cdot 2^{w})\,,$$

where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, and $w$ is the log of the largest element, so both are variables.)

What kind of growth does this function have? I'll say it is exponential, however I don't know what the 0.24 implies.

• Also, this question has nothing to do with time complexity. $O()$ is a notation for classes of functions. Those functions could be used to measure anything at all: the population of a bacterial colony, for example. – David Richerby Oct 4 '17 at 8:45
• @David Richerby thank you for the edits, won't be a problem to disconnect edits from the answers? For instance I edited the question and now the answers are bit missaligned, on another stack* forums we chose this way of "version" a question to provide information about why people answered in a specific way, I'll stick to your suggestion anyway. – Jesus Salas Oct 4 '17 at 16:40
• @JesusSalas The edit I made didn't disconnect because all it did was clarify. But your more recent edit has changed the question and people will wonder why all the answers are talking about $0.24K$ when the question says $K/4$... – David Richerby Oct 4 '17 at 17:52
• @David Richerby you are completely right, thanks for reverting back, this let the question be more consistent – Jesus Salas Oct 4 '17 at 18:40
• @JesusSalas You may want to check out this and this question. Bottom line: few people know what they are doing when they use multi-parameter Landau notation. – Raphael Oct 4 '17 at 20:40

If $K$ is constant and $w$ is variable then $0.24\times K\times 2^w$ and the function is exponential in $w$, therefore it is $O(2^w)$.

If $K$ is variable and $w$ is constant then $0.24\times K\times 2^w$ is $O(K)$ - linear in $K$.

If both $K$ and $w$ are variables then $0.24\times K\times 2^w$ is $O(K2^w)$.

If both $K$ and $w$ are constant then $0.24\times K\times 2^w$ is $O(1)$.

The constant $0.24$ is ignored since it becomes irrelevant when we compare the rate of growth of a function. For more details please see Big-O notation.

We also use $O^*(f(n))$ notation, in particular in analysis of parametrized algorithms, which means that the algorithm runs in $O(f(n)p(k))$ for some polynomial $p(k)$. So you could also write it is $O^*(2^w)$ in case $w$ is variable.

• Ah, right , I didn't remember we eliminate constants in the BIG-O notation, thanks! – Jesus Salas Oct 4 '17 at 6:30

The function $f(K,w) = K\cdot 2^w$ has polynomial (in fact, linear) dependence on $K$ and exponential dependence on $w$.

You're interested in the function $g(K,w) = 0.24\cdot f(K,w)$ but the constant multiplier doesn't change anything. Linear growth in $K$ means that, if $K$ doubles, then $f(K,w)$ doubles, too. But doubling $K$ also doubles $g(K,w)$. Exponential growth (with base $2$) means that adding $1$ to $w$ doubles $f(K,w)$, and the same applies to $g$.