1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 4 '17 at 8:45
  • $\begingroup$ @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. $\endgroup$ – Jesus Salas Oct 4 '17 at 16:40
  • 1
    $\begingroup$ @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$... $\endgroup$ – David Richerby Oct 4 '17 at 17:52
  • 1
    $\begingroup$ @David Richerby you are completely right, thanks for reverting back, this let the question be more consistent $\endgroup$ – Jesus Salas Oct 4 '17 at 18:40
  • 1
    $\begingroup$ @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. $\endgroup$ – Raphael Oct 4 '17 at 20:40
2
$\begingroup$

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.

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

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

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