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.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.