I want to ask how does GAP calculate the irreps? I guess the answer is that GAP realizes groups as permutation groups (or sometimes linear groups), then there is some efficient algorithm for permutation groups.
Does such an algorithm exist? If so, what is the algorithm called? What is the asymptotic behavior of the complexity. Does it work if we replace $\mathbb{C}$ with a finite field of characteristic dividing the group order (I assume it can, because GAP can calculate modular characters as well, but is it the same algorithm?)
(It took me 30 seconds to compute the character table of a group of order $24200$.)
Assuming you have a finite group and you ask for the calculation of irreducible characters over $\mathbb C$, GAP will as default method use the Dixon-Schneider algorithm: [MR1075426, Schneider, Gerhard J. A. Dixon's character table algorithm revisited. J. Symbolic Comput. 9 (1990), no. 5-6, 601–606.] (If the group is nilpotent the Baum/Clausen algorithm is used.)
This is inherently a method in the space of class functions without constructing actual representations.
As for asymptotic behavior, the runtime for all algorithms for ordinary character tables that I am aware of is dominated by the identification of conjugacy classes in which given elements lie. The cost of this depends very much on the group (e.g. it is trivial in the full symmetric group). While it behaves well in practice it often builds fundamentally on a backtrack search that scales exponential in e.g. the permutation degree.
(The second most expensive task then is linear algebra in the space of class functions.)
For modular characters the methods are very different and (as Derek Holt wrote) much harder -- in general it is necessary to construct the actual representations first.