  The Murnaghan-Nakayama rule is the classical formula for computing the
character table of S_n. Y. Roichman has recently discovered a rule for the
Kazhdan-Lusztig characters of q-Hecke algebras of type A, which can also be
used for the character table of S_n. For each of the two rules, we give an
algorithm for computing entries in the character table of S_n. We then analyze
the computational complexity of the two algorithms, and in the case of
characters indexed by partitions in the (k,l)-hook, compare their complexities
to each other. It turns out that the algorithm based on the Murnaghan-Nakayama
rule requires far less operations than the other algorithm. We note the
algorithms' complexities' relation to two enumeration problems of Young
diagrams and Young tableaux.
