Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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)$.
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.
