In this paper, we propose a general methodology for designing fixed order controllers for single-input single-output plants. The controller parameters are classified into two classes: randomized and deterministically designed. For the first class, we study randomized algorithms. In particular, we present two low-complexity algorithms based on the Chernoff bound and on a related bound (often called "log-over-log" bound) which is generally used for optimization problems. Secondly, for the deterministically designed parameters, we reformulate the original problem as a set of linear equations. Then, we develop a technique which efficiently solves it using a combination of matrix inversions and sensitivity methods. A detailed complexity analysis of this technique is carried on, showing its superiority (from the computational point of view) to existing algorithms based on linear programming. In the second part of the paper, these results are extended to H-infinity performance. One of the contributions is to prove that the deterministically designed parameters enjoy a special convex characterization. This characterization is then exploited in order to design fixed order controllers efficiently. We then show further extensions of these methods for stabilization of interval plants. In particular, we derive a simple one-parameter formula for computing the so-called critical frequencies which are required by the algorithms.