Is Big-O (and Omega and Theta) ever used for other algorithm cost parameters besides time? Like, could I usefully describe different presentation methodologies in terms of bandwidth consumption per n bytes of content as O (n log n) for example? Or is there a separate notation?

Sure it's used for other things. The most common is space, as noted by the other commenters.

In a streaming setting (where you can only read through the data in one direction, in order) you might describe O(f(n)) passes as required for some algorithm. You might also describe some distributed/network algorithm in terms of bits of communication.

As the other people said, Big-O/Small-O/Theta/Omega notation is also used for space commonly. It really can be used for anything though. I've seen it used for population growth and other non-computational things. It is also used to measure growth rates of infinite sequences in Calculus (so "math").

In my distributed multimedia class, we used Big-O (and others) all the time for both space and bandwidth. A common usage would be as follows:

(1) Calculate the packet arrival time for a given network and the necessary rate of media playback for a given profile (i.e. bitrate, quality, encoding,e tc). (2) Put a Big-O on each (3) From (2), put a Big-O on the amount of memory you'd need in your set top box to buffer, given a certain tolerance for loss of playback or dropped frames.

karinfromnosundMay 21 2009, 11:19:12 UTC 8 years ago

So the answer is: yes, go ahead.

rxvmMay 21 2009, 11:23:59 UTC 8 years ago

czarandyMay 21 2009, 12:45:49 UTC 8 years ago

In a streaming setting (where you can only read through the data in one direction, in order) you might describe O(f(n)) passes as required for some algorithm. You might also describe some distributed/network algorithm in terms of bits of communication.

danman3459May 21 2009, 13:51:30 UTC 8 years ago

czarandyMay 21 2009, 14:58:42 UTC 8 years ago

For example, the prime number theorem says that the density of primes grows like (1 + o(1))(n/ln(n)).

roadriverrailMay 21 2009, 17:50:20 UTC 8 years ago

(1) Calculate the packet arrival time for a given network and the necessary rate of media playback for a given profile (i.e. bitrate, quality, encoding,e tc).

(2) Put a Big-O on each

(3) From (2), put a Big-O on the amount of memory you'd need in your set top box to buffer, given a certain tolerance for loss of playback or dropped frames.