31

Help! I have a question where I need to analyze the Big-O of an algorithm or some code.

  • I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's complexity.

  • I am unsure whether Big-O refers to the time to run the code, or the amount of memory it takes (space/time tradeoffs).

  • I have Computer Science homework where I need to take some loops, perhaps a recursive algorithm, and come up with the Big-O for it.

  • I am working on a program where I have a choice between two data structures or algorithms with a known Big-O, and am unsure which one to choose.

How do I understand how to calculate and apply Big-O to my program, homework, or general knowledge of Computer Science?

Note: this question is a canonical dupe target for other Big-O questions as determined by the community. It is intentionally broad to be able to contain a large amount of useful information for many Big-O questions. Please do not use the fact that it is this broad as an indication that similar questions are acceptable.

  • 1
    Just a note, this question is being discussed on meta here. – enderland Oct 28 '15 at 20:14
  • 2
    A great resource to get started would be the Khan academy course (Thomas Cormen of CLRS is one of the writers). This was a great resource for me as a CS grad too. khanacademy.org/computing/computer-science/algorithms – Sudip Bhandari Oct 5 '16 at 9:54
  • 3
    To the people flagging this question: please read the subtext at the bottom of the question, and follow that link before flagging or voting to close. – user22815 Jan 24 '17 at 16:08
22

The O(...) refers to Big-O notation, which is a simple way of describing how many operations an algorithm takes to do something. This is known as time complexity.

In Big-O notation, the cost of an algorithm is represented by its most costly operation at large numbers. If an algorithm took n3 + n2 + n steps, it would be represented O(n3). An algorithm that counted each item in a list would operate in O(n) time, called linear time.

For a list of the names and classic examples on Wikipedia: Orders of common functions

Related material:

  • 6
    Note: big O doesn't inherently measure time or space or any particular thing. It simply upper bounds the asymptotic growth of a function (up to a constant). That function could be the time, space, etc. of an algorithm as a function of its input length, and most commonly in a CS context is the time, but isn't necessarily. – Solomonoff's Secret May 19 '16 at 20:39
23

What are the asymptotic functions? What is an asymptote, anyway?

Given a function f(n) that describes the amount of resources (CPU time, RAM, disk space, etc) consumed by an algorithm when applied to an input of size of n, we define up to three asymptotic notations for describing its performance for large n.

An asymptote (or asymptotic function) is simply some other function (or relation) g(n) that f(n) gets increasingly close to as n grows larger and larger, but never quite reaches. The advantage of talking about asymptotic functions is that they are generally much simpler to talk about even if the expression for f(n) is extremely complicated. Asymptotic functions are used as part of the bounding notations that restrict f(n) above or below.

(Note: in the sense employed here, the asymptotic functions are only close to the original function after correcting for some constant nonzero factor, as all the three big-O/Θ/Ω notations disregard this constant factors from their consideration.)

What are the three asymptotic bounding notations and how are they different?

All three notations is used like this:

f(n) = O(g(n))

where f(n) here is the function of interest, and g(n) is some other asymptotic function that you are trying to approximate f(n) with. This should not be taken as an equality in a rigorous sense, but a formal statement between how fast f(n) grows with respect to n in comparison to g(n), as n becomes large. Purists will often use the alternative notation f(n) ∈ O(g(n)) to emphasize that the symbol O(g(n)) is really a whole family of functions that share a common growth rate.

Big-ϴ (Theta) notation states an equality on the growth of f(n) up to a constant factor (more on this later). It behaves similar to an = operator for growth rates.

Big-O notation describes an upper-bound on the growth of f(n). It behaves similar to a operator for growth rates.

Big-Ω (Omega) notation describes a lower-bound on a growth of f(n). It behaves similar to a operator for growth rates.

There are many other asymptotic notations, but they do not occur nearly as often in computer science literature.

Big-O notations and its ilk are often as a way to compare the time complexity.

What is time complexity?

Time complexity is a fancy term for the amount of time T(n) it takes for an algorithm to execute as a function of its input size n. This can be measured in the amount of real time (e.g. seconds), the number of CPU instructions, etc. Usually it is assumed that the algorithm will run on your everyday von Neumann architecture computer. But of course you can use time complexity to talk about more exotic computing systems, where things may be different!

It is also common to talk about space complexity using Big-O notation. Space complexity is the amount of memory (storage) required to complete the algorithm, which could be RAM, disk, etc.

It may be the case that one algorithm is slower but uses less memory, while another is faster but uses more memory. Each may be more appropriate in different circumstances, if resources are constrained differently. For example, an embedded processor may have limited memory and favor the slower algorithm, while a server in a data center may have a large amount of memory and favor the faster algorithm.

Calculating Big-ϴ

Calculating the Big-ϴ of an algorithm is a topic that can fill a small textbook or roughly half a semester of undergraduate class: this section will cover the basics.

Given a function f(n) in pseudocode:

int f(n) {
  int x = 0;
  for (int i = 1 to n) {
    for (int j = 1 to n) {
      ++x;
    }
  }
  return x;
}

What is the time complexity?

The outer loop runs n times. For each time the outer loop runs, the inner loop runs n times. This puts the running time at T(n) = n2.

Consider a second function:

int g(n) {
  int x = 0;
  for (int k = 1 to 2) {
    for (int i = 1 to n) {
      for (int j = 1 to n) {
        ++x;
      }
    }
  }
  return x;
}

The outer loop runs twice. The middle loop runs n times. For each time the middle loop runs, the inner loop runs n times. This puts the running time at T(n) = 2n2.

Now the question is, what is the asymptotic running time of both functions?

To calculate this, we perform two steps:

  • Remove constants. As algorithms increase in time due to inputs, the other terms dominate the running time, making them unimportant.
  • Remove all but the largest term. As n goes to infinity, n2 rapidly outpaces n.

They key here is focus on the dominant terms, and simplify to those terms.

T(n) = n2 ∈ ϴ(n2)
T(n) = 2n2 ∈ ϴ(n2)

If we have another algorithm with multiple terms, we would simplify it using the same rules:

T(n) = 2n2 + 4n + 7 ∈ ϴ(n2)

The key with all of these algorithms is we focus on the largest terms and remove constants. We are not looking at the actual running time, but the relative complexity.

Calculating Big-Ω and Big-O

First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ, perhaps because Greek letters are tricky to type. So if someone out of the blue asks you for the Big-O of an algorithm, they probably want its Big-Θ.

Now if you really do want to calculate Big-Ω and Big-O in the formal senses defined earlier, you have a major problem: there are infinitely many Big-Ω and Big-O descriptions for any given function! It's like asking what the numbers that are less than or equal to 42 are. There are many possibilities.

For an algorithm with T(n) ∈ ϴ(n2), any of the following are formally valid statements to make:

  • T(n) ∈ O(n2)
  • T(n) ∈ O(n3)
  • T(n) ∈ O(n5)
  • T(n) ∈ O(n12345 × en)
  • T(n) ∈ Ω(n2)
  • T(n) ∈ Ω(n)
  • T(n) ∈ Ω(log(n))
  • T(n) ∈ Ω(log(log(n)))
  • T(n) ∈ Ω(1)

But it is incorrect to state T(n) ∈ O(n) or T(n) ∈ Ω(n3).

What is relative complexity? What classes of algorithms are there?

If we compare two different algorithms, their complexity as the input goes to infinity will normally increase. If we look at different types of algorithms, they may stay relatively the same (say, differing by a constant factor) or may diverge greatly. This is the reason for performing Big-O analysis: to determine if an algorithm will perform reasonably with large inputs.

The classes of algorithms break down as follows:

  • Θ(1) - constant. For example, picking the first number in a list will always take the same amount of time.

  • Θ(n) - linear. For example, iterating a list will always take time proportional to the list size, n.

  • Θ(log(n)) - logarithmic (base normally does not matter). Algorithms that divide the input space at each step, such as binary search, are examples.

  • Θ(n × log(n)) - linear times logarithmic (“linearithmic”). These algorithms typically divide and conquer (log(n)) while still iterating (n) all of the input. Many popular sorting algorithms (merge sort, Timsort) fall into this category.

  • Θ(nm) - polynomial (n raised to any constant m). This is a very common complexity class, often found in nested loops.

  • Θ(mn) - exponential (any constant m raised to n). Many recursive and graph algorithms fall into this category.

  • Θ(n!) - factorial. Certain graph and combinatorial algorithms are factorial complexity.

Does this have anything to do with best/average/worst case?

No. Big-O and its family of notations talk about a specific mathematical function. They are mathematical tools employed to help characterize the efficiency of algorithms, but the notion of best/average/worst-case is unrelated to the theory of growth rates described here.

To talk about the Big-O of an algorithm, one must commit to a specific mathematical model of an algorithm with exactly one parameter n, which is supposed to describe the “size” of the input, in whatever sense is useful. But in the real world, inputs have much more structure than just their lengths. If this was a sorting algorithm, I could feed in the strings "abcdef", "fedcba", or "dbafce". All of them are of length 6, but one of them is already sorted, one is reversed, and the last is just a random jumble. Some sorting algorithms (like Timsort) work better if the input is already sorted. But how does one incorporate this inhomogeneity into a mathematical model?

The typical approach is to simply assume the input comes from some random, probabilistic distribution. Then, you average the algorithm's complexity over all inputs with length n. This gives you an average-case complexity model of the algorithm. From here, you can use the Big-O/Θ/Ω notations as usual to describe the average case behavior.

But if you are concerned about denial-of-service attacks, then you might have to be more pessimistic. In this case, it is safer to assume that the only inputs are those that cause the most amount of grief to your algorithm. This gives you a worst-case complexity model of the algorithm. Afterwards, you can talk about Big-O/Θ/Ω etc of the worst-case model.

Similarly, you can also focus your interest exclusively to the inputs that your algorithm has the least amount of trouble with to arrive at a best-case model, then look at Big-O/Θ/Ω etc.

  • This is a good answer, but Big-O and Big-Ω have little to do with worst and best cases. They are upper and lower bounds, but they can both apply to either case, for instance, insertion sort has, in the best case, a time complexity of ϴ(n) (both Big-O and Big-Ω) while having, in the worst case, a time complexity of ϴ(n²) (both Big-O and Big-Ω). – Paul Aug 4 '16 at 4:10
  • Also, any algorithm, excluding the empty algorithm, is Ω(1) in the best, worst, and average cases, but that is because that is a lower bound and doesn't have anything to do with the actual best case of the algorithm. – Paul Aug 4 '16 at 4:12
  • Big-whatever have nothing to do with best or worst case – this is a common misconception. They are merely ways to state whether a deterministic functions grows faster, slower, or at the same rate in comparison to another. The notion of best/worst case only exist once you start talking about the time/space complexity of real algorithms, in which case the non-deterministic factors arise and you need to consider the probability distribution of your inputs. Even then, best/worst case lies on an axis orthogonal to big-O/Omega. – Rufflewind Jan 23 '17 at 23:16
  • @Rufflewind if you think you can describe it better, then go ahead. You do realize this is a community wiki answer, right? – user22815 Jan 23 '17 at 23:22
  • "First off, be warned that in informal literature, “Big-O” is often treated as a synonym for Big-Θ" -> Not only in informal literature. My first semester on Complexity, back in college, taught us the definition of Big-O as if it was Big-Θ. (Our textbook used that definition!) It confused the hell out of me when I went to Complexity II and I found out the two weren't the same. – T. Sar - Reinstate Monica Nov 7 '18 at 18:55

protected by Thomas Owens Oct 28 '15 at 19:49

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.