## 16 August 2008

### Oh, Theta!

[Edit: Rewrote to more accurately reflect the story that prompted this post.]

I read O(f(n)) as (degree) at most f(n), Ω(f(n)) as (degree) at least f(n), and Θ(f(n)) as (degree) f(n). (I omit ‘degree’ when I’m lazy. That is, most of the time.)

If I describe amortized complexity I might say that a sequence of n operations takes at most degree n time, and each individual operation may take degree n time. I would write this as: A sequence of n operations takes O(n) time, and

• one operation may take Θ(n) time.
• one operation may take Ω(n) time.
• each operation also takes O(n) time.

but not:

• one operation may take O(n) time.