Computability and Complexity with Inexact Real Arithmetic, Part II

I will:

• Briefly finish talking about the classification of the asymptotically computable functions

• Describe the asymptotic model of computation with interval arithmetic

• Define computational complexity for computations in the asymptotic model and the recursive analysis model

• Prove a theorem relating computational complexity in the two models

• Give an example of how to analyze the running time of an algorithm in the asymptotic model