# Should I keep a relevant constant in the Time Complexity?

I designed an algorithm, and the Time Analysis provided next time complexity:

$$\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$$

what must be simplified to:

$$\mathcal{O}(2^p \cdot \frac{n^2}{16})$$ = $$\mathcal{O}(2^p \cdot n^2)$$

That constant factor is quite relevant in this case, and the only reason I'm considering keeping it, is because represents an important fact of the algorithm behavior.

• If that constant is important, it means it's not a constant, it's a variable. Be careful while picking basic operations. – ferit Sep 23 '18 at 23:18

## 1 Answer

In asymptotic notation constant factors are "modded out". For example, an algorithm runs in time $$O(n)$$ iff it runs in time $$O(2n)$$ iff it runs in time $$O(n/2)$$.

If you want to capture such a difference meaningfully, you have (at least) two options:

1. Add another parameter. There could be a parameter $$t$$ such that your algorithm runs in time $$O(tn)$$. One way to think about it is that the algorithm runs in time $$O_t(n)$$, i.e., with a big O constant that depends on $$t$$, and the dependence on the big O constant on $$t$$ is $$O(t)$$.

2. Count a specific operation. In some cases you might be able to count a specific type of operation more accurately. For example, perhaps one sorting algorithm performs $$(2 \pm o(1)) n\log n$$ comparisons on average, and another performs $$(3 \pm o(1)) n\log n$$ comparisons on average.