RNAfold Time сложность в пакете VinnaRNA

В предоставленной вами ссылке есть эмпирический анализ времени выполнения. Вы можете увидеть линейное время вычислений на диаграмме.

Это означает, что вы можете написать (используя log для логарифма в базе 10 и вызова T временная сложность алгоритма)

   log(T(10^n)) = a.n + b                          for a and b to be read from the graph
=> T(10^n) = 10^(a.n + b) = C.10^(a.n)             with C constant
=> T(n) = T(10^(log(n)) = C.10^(a.log(n)) = C.n^a

Теперь, читая график, вы можете увидеть, что

• T(length of RNA sequence = 1000) ~= 10^0 = 1
• T(10000) ~= 10^2.6

Что даст вам приближение a ~= 2.6
Если вы хотите быть консервативным, вы можете связать a с 3 что приводит к сложности

T(n) = O(n^3)

куда n длина последовательности РНК в нуклеотидах.