  Multiphase ranking functions ($\mathit{M{\Phi}RFs}$) were proposed as a means
to prove the termination of a loop in which the computation progresses through
a number of "phases", and the progress of each phase is described by a
different linear ranking function. Our work provides new insights regarding
such functions for loops described by a conjunction of linear constraints
(single-path loops). We provide a complete polynomial-time solution to the
problem of existence and of synthesis of $\mathit{M{\Phi}RF}$ of bounded depth
(number of phases), when variables range over rational or real numbers; a
complete solution for the (harder) case that variables are integer, with a
matching lower-bound proof, showing that the problem is coNP-complete; and a
new theorem which bounds the number of iterations for loops with
$\mathit{M{\Phi}RFs}$. Surprisingly, the bound is linear, even when the
variables involved change in non-linear way. We also consider a type of
lexicographic ranking functions, $\mathit{LLRFs}$, more expressive than types
of lexicographic functions for which complete solutions have been given so far.
We prove that for the above type of loops, lexicographic functions can be
reduced to $\mathit{M{\Phi}RFs}$, and thus the questions of complexity of
detection and synthesis, and of resulting iteration bounds, are also answered
for this class.
