Moral Explorer (notthebuddha) wrote in algorithms,
Moral Explorer

Big-O for other parameters?

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?
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

You see them used for space sometimes. O(f(n)) describes a function -- not a specific characteristic.

So the answer is: yes, go ahead.
Big-O can describe asymptotic behavior of any function. For example, it is used for space complexity of algorithms.
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").
Another use is to use little-o for error terms in math.

For example, the prime number theorem says that the density of primes grows like (1 + o(1))(n/ln(n)).
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.