1
$\begingroup$

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.

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

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.

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