The aim of this work is to develop the tool of logical deduction schemata and use it to establish upper and lower bounds on the complexity of proofs and their transformations in axiomatized theories. The main results are: establishment of upper bounds on the elongation of deductions in cut eliminations; a proof that the length of a direct deduction of an existence theorem in the predicate calculus cannot be bounded above by an elementary function of the length of an indirect deduction of the same theorem; a complexity version of the existence property of the constructive predicate calculus;...