  In this paper, we develop new algorithms for the basic RNA folding problem.
Given an RNA sequence that contains $n$ nucleotides, the goal of the problem is
to compute a pseudoknot-free secondary structure that maximizes the number of
base pairs in the sequence. We show that there exists a dynamic programming
algorithm that can solve the problem in time $O(\frac{n^{3}}{\log_{2}{n}})$
while using only $O(\frac{n^{2}}{\log_{2}{n}})$ memory space. In addition, we
show that the time complexity of this algorithm can be further improved to
$O(\frac{n^{3}}{\log_{2}^{2}{n}})$ at the expense of a slightly increased space
complexity. To the best of our knowledge, this is the first algorithm that can
solve the problem with traditional dynamic programming techniques in time
$O(\frac{n^{3}}{\log_{2}^{2}{n}})$. In addition, our results improve the best
known upper bound of the space complexity for efficiently solving both this
problem and the context-free language recognition problem.
