Towards Complexity Analysis of Programs by Rewriting In this talk I'll report on recent work on a complexity analysis of Java Bytecode programs by rewriting. The idea here is to show that the transformation from JBC programs to rewriting as recently proposed by Otto et al. is complexity preserving in the sense that the complexity of the obtained rewrite system allows to judge the runtime complexity of the initial JBC program. Although we cannot make use of the full power of the termination techniques employed by Otto et al. similar (but weaker) results can be obtained for complexity analyis.