Moral Explorer (notthebuddha) wrote in algorithms,

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

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 6 comments

karinfromnosund

May 21 2009, 11:19:12 UTC 5 years ago

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

So the answer is: yes, go ahead.

rxvm

May 21 2009, 11:23:59 UTC 5 years ago

Big-O can describe asymptotic behavior of any function. For example, it is used for space complexity of algorithms.

czarandy

May 21 2009, 12:45:49 UTC 5 years ago

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.

danman3459

May 21 2009, 13:51:30 UTC 5 years ago

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").

czarandy

May 21 2009, 14:58:42 UTC 5 years ago

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)).

roadriverrail

May 21 2009, 17:50:20 UTC 5 years ago

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.