Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
1  
Just a note, this question is being discussed on meta here. – enderland Oct 28 '15 at 20:14
up vote 15 down vote accepted

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:

share|improve this answer
    
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 at 20:39

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

Given a function f(n) that implements an algorithm, we define up to three asymptotic notations for measuring its performance. An asymptote is simply some other function (or relation) g(n) that f(n) gets close to, but never quite reaches. This is used to determine bounding functions that contain f(n) above or below.

What are the three asymptotic functions and how are they different?

Big-O notation is concerned with the worst case complexity of an algorithm: it is an upper-bound on the complexity of f(n).

Big-Ω (Omega) is the opposite: it is the best case. An algorithm may be really efficient for certain inputs, or it may take just as long as the worst case. Regardless, this is the lower-bound on a complexity of f(n).

Big-ϴ (Theta) is applicable to a function where the best and worst case are the same, differing only by a constant factor (more on this later). If a function scales the same regardless of the input, it has O(n) = Ω(n) → ϴ(n)

What type of complexity do they measure?

Complexity is typically measured in the amount of time for f(n) to execute as it scales with the input n, or more specifically, the number of steps T(n) to complete the algorithm. However, it may also measure the amount of memory (storage) required to complete the algorithm.

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-O

Calculating the Big-O 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 → O(n2)
T(n) = 2n2 → O(n2)

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

T(n) = 2n2 + 4n + 7 → O(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-ϴ

Calculating Big-Ω is similar to Big-O, except one figures out "what is the best outcome at each step?" This is normally done if there is any way to shortcut the logic: is there a decision at a particular step instead of blindly iterating? If it is possible to eliminate part of the input, the best-case may be better than the worst-case.

It may be the case that an algorithm is always the same complexity. The best and worst cases have the same algorithmic complexity: perhaps they differ only by a constant. In the asymptotic measurement, they scale the same way. For example, searching for the minimum or maximum value in an unsorted list always requires n time: such an algorithm is Ω(n) and O(n). If this is the case, the algorithm is also ϴ(n): its upper and lower bounds are the same, ϴ(n).

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:

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

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

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

  • O(n log n) - linear times logarithmic. 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.

  • O(nm) - polynomial (n raised to any constant m). This is a very common complexity class.

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

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

share|improve this answer

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.