0
$\begingroup$

A non-recursive linear Suffix Array construction algorithm is presented in this thesis: Linear-time Suffix Sorting. The author claims that, overall, the algorithm runs at $O(n)$. While it is well explained, there are only hints that this is case. The implementation of the algorithm is in this GitHub repository written in C.

My question is: What are the complexity constants (say $O(\alpha n + \beta)$ where $\alpha$ and $\beta$ are constants) for C code between lines 92 and 186?

$\endgroup$
1
$\begingroup$

Constants like this are generally not calculated for the run time of algorithms, because it's not clear what they would count - would they count the number of some sort of primitive C operation executed, or the number of x86-64 operations, or the number of arm64 operations, or the microcode operations, or ...?

More frequently than calculating the constants, people measure the run time and show the $\alpha$ that fits best. They will also sometimes calculate the number of times a specific operation is executed, like comparisons or swaps in a sorting algorithm.

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