Big-O Notation Explained with Java Examples

Introduction

Every programmer sooner or later asks the same question - "my code works, but will it still work when there is a hundred times more data?" Big-O notation is the tool for answering it. In this tutorial we will build the idea step by step. We start with an everyday question, see why a stopwatch is the wrong tool to answer that question, learn to count steps instead, and then arrive at the formal definition. After that we go through the common complexities with Java programs which count their own steps, learn how to find the Big-O of any piece of code, practise on four questions, and finish with best and worst cases and space complexity. Every number shown in the tutorial comes from running the program next to it.

A Question Before the Definition

Imagine a class of 30 students, and I ask you to find the student whose roll number is 17. How would you do it? Think about it for a moment before reading on.

There are at least three ways -
  • Ask everybody. Go from student to student and ask "are you number 17?" until someone says yes. If you are unlucky it is the last student, and you asked 30 times. For a class of 30 million you may have to ask 30 million times. The work grows in step with the size of the class.
  • Use the fact that the roll list is in order. Open the list in the middle - roll number 15. Seventeen is higher, so the first half is forgotten. Open the middle of the remaining half, and so on. Each question throws away half of what is left. For 30 students that is about 5 questions. For 30 million students it is about 25. The class became a million times bigger, and the work grew by only 20 questions.
  • Know where each student sits. If the seat of every roll number is written on a chart, the answer is one look at the chart, whether the class has 30 students or 30 million.
Three ways to find roll number 17 in a class - asking every student one by one takes up to n questions, repeatedly opening the middle of an ordered roll list and forgetting half takes about log n questions, and looking the student up on a seating chart takes one look whatever the size of the class Notice what we did. We did not measure minutes or seconds. We asked a different question: when the class becomes larger, how does the amount of work grow? The first way grows with the class, the second grows very slowly, and the third does not grow at all. Big-O notation is the language for exactly these three answers, and we will see in a moment that they are written O(n), O(log n) and O(1).

Why Not Just Use a Stopwatch

A student might say "simple - run both programs and note the time". The trouble is that the time does not belong to the algorithm alone. Two of you running the same program get different times, because -
  • your computers have different speeds,
  • the Java version, the memory and the other programs which are running are different,
  • the time depends on the input you happened to choose, and a small input can make a poor algorithm look good.
What stays the same on every computer is the number of steps the algorithm has to take for an input of a given size. A step is a basic operation - one comparison, one addition, one array access. So the plan is - count the steps, and see how the count changes as the input size grows. The size of the input is written as n: the number of students, the number of items in a list, the number of characters in a string.

Counting Steps

Lets count the steps of a very simple method, which adds up the numbers of an array. The program below has a counter, steps, which is increased every time the method does one basic thing.
Counting the steps of a method
package com.javabrahman.algorithms.bigo;
public class HandCount {
  static long steps;
  static int sum(int[] data) {
    int total = 0;
    steps++;
    for (int i = 0; i < data.length; i++) {
      total += data[i];
      steps++;
    }
    steps++;
    return total;
  }
  public static void main(String[] args) {
    System.out.printf("%8s %8s%n", "n", "steps");
    for (int n : new int[] { 5, 10, 100, 1000 }) {
      steps = 0;
      sum(new int[n]);
      System.out.printf("%8d %8d%n", n, steps);
    }
  }
}
 OUTPUT of the above code
       n    steps
       5        7
      10       12
     100      102
    1000     1002
In the above output, the method does one step to set total to 0, one step for every item of the array, and one step for the return. So for n items it takes n + 2 steps - 7 for n = 5, 1002 for n = 1000. We have a formula for the work as a function of the input size, and that is the first half of Big-O.

Which Part of the Formula Matters

Now a second question. We found n + 2. Does the "+ 2" matter? Look at the table - for n = 1000 the total is 1002, and the 2 is a fifth of one percent of it. When the input is a million items, the 2 is invisible. So we throw it away: only the part which grows the fastest matters. What if the method did 3 steps for every item instead of one - 3n + 2 steps? It would be three times slower, but when the input doubles the work still doubles, just as before. The 3 changes how fast the line is, not what shape it has. So we throw away the constant multiplier as well, and say both methods are "of the order n". This is the whole idea behind the two simplifications of Big-O notation -
  • Drop the constants. 3n and 100n are both O(n).
  • Keep only the fastest growing term. n2 + n + 7 is O(n2).
We will check both simplifications on a real method in the next section, after we have seen the formal definition they come from.

The Formal Definition

Now that the idea is clear, here is the definition which a textbook would have started with. We say that f(n) is O(g(n)) if there are two numbers, a constant c and a starting point n0, such that
f(n) ≤ c × g(n) for every n ≥ n0
In words: after some starting size n0, the real work f(n) never goes above a constant multiple of the simple function g(n). Here f(n) is the exact number of steps, and g(n) is the simple shape we want to name it with, such as n or n2. Big-O is therefore an upper limit. Lets prove that 3n2 + 5n + 2 is O(n2) by choosing c = 4. We need 3n2 + 5n + 2 ≤ 4n2, which is the same as n2 - 5n - 2 ≥ 0. This is true from n = 6 onwards, so n0 = 6. The method in the program below does 3 steps for every pair of items in a loop inside a loop, then 5 steps for every item in a single loop, and then 2 more steps - so its work is exactly 3n2 + 5n + 2. The program counts these steps for real, divides them by n2, and checks the inequality for c = 4 -
Dropping the constants and the smaller terms
package com.javabrahman.algorithms.bigo;
public class DroppingTerms {
  static long steps(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        steps += 3;
      }
    }
    for (int i = 0; i < n; i++) {
      steps += 5;
    }
    steps += 2;
    return steps;
  }
  public static void main(String[] args) {
    System.out.printf("%8s %14s %14s %10s %12s%n", "n", "steps", "steps / n*n", "4 * n*n", "steps<=4n*n");
    for (int n : new int[] { 1, 2, 5, 6, 10, 100, 1000, 10000 }) {
      long steps = steps(n);
      long limit = 4L * n * n;
      System.out.printf("%8d %14d %14.4f %10d %12b%n", n, steps, (double) steps / ((long) n * n), limit, steps <= limit);
    }
  }
}
 OUTPUT of the above code
       n          steps    steps / n*n    4 * n*n  steps<=4n*n
       1             10        10.0000          4        false
       2             24         6.0000         16        false
       5            102         4.0800        100        false
       6            140         3.8889        144         true
      10            352         3.5200        400         true
     100          30502         3.0502      40000         true
    1000        3005002         3.0050    4000000         true
   10000      300050002         3.0005  400000000         true
Look at the output in two ways. In the third column the steps divided by n2 start at 10 for n = 1 and settle down to 3.0005 for n = 10000 - the 5n and the 2 are fading away, and 3n2 is what remains. In the last column you can see the definition at work: for n = 1, 2 and 5 the work is above 4n2, and from n = 6 onwards it is below it, and stays below it. This is exactly why we needed the starting point n0. Big-O notation does not worry about small inputs; it is a statement about what happens as n grows.

The Common Complexities with Java Examples

With this idea in hand, these are the complexities you will meet most often, from the slowest growing to the fastest growing. Each of them has a Java method in the program which follows.
Counting the steps for each complexity
package com.javabrahman.algorithms.bigo;
public class GrowthTable {
  static long constant(int n) {
    int[] data = new int[n];
    long steps = 0;
    int first = data[0];
    steps++;
    return steps;
  }
  static long logarithmic(int n) {
    long steps = 0;
    for (int size = n; size > 1; size = size / 2) {
      steps++;
    }
    return steps;
  }
  static long linear(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      steps++;
    }
    return steps;
  }
  static long linearithmic(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int size = n; size > 1; size = size / 2) {
        steps++;
      }
    }
    return steps;
  }
  static long quadratic(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        steps++;
      }
    }
    return steps;
  }
  static long exponentialCalls;
  static int fib(int n) {
    exponentialCalls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.printf("%8s %8s %8s %10s %14s %14s%n", "n", "O(1)", "O(log n)", "O(n)", "O(n log n)", "O(n*n)");
    for (int n : new int[] { 10, 100, 1000, 10000 }) {
      System.out.printf("%8d %8d %8d %10d %14d %14d%n", n, constant(n), logarithmic(n), linear(n), linearithmic(n), quadratic(n));
    }
    System.out.println();
    System.out.printf("%8s %20s%n", "n", "recursive calls O(2^n)");
    for (int n : new int[] { 10, 20, 30, 35 }) {
      exponentialCalls = 0;
      fib(n);
      System.out.printf("%8d %20d%n", n, exponentialCalls);
    }
  }
}
 OUTPUT of the above code
       n     O(1) O(log n)       O(n)     O(n log n)         O(n*n)
      10        1        3         10             30            100
     100        1        6        100            600          10000
    1000        1        9       1000           9000        1000000
   10000        1       13      10000         130000      100000000

       n recursive calls O(2^n)
      10                  177
      20                21891
      30              2692537
      35             29860703
In the above table, take the first row, n = 10, and the last, n = 10000. The input became a thousand times larger. In that time -
  • O(1) took the same 1 step.
  • O(log n) went from 3 to 13 steps - only 10 more.
  • O(n) went from 10 to 10,000 steps - a thousand times more.
  • O(n log n) went from 30 to 130,000 steps - about four thousand times more.
  • O(n2) went from 100 to 100,000,000 steps - a million times more.
The second table is the exponential one. The calls grow from 177 for n = 10 to almost 30 million for n = 35. Each increase of n by 1 multiplies the calls by about 1.6. For n = 50 the method would make more than 40 billion calls. This is why exponential algorithms are usable only for very small inputs. The growth of the common complexities as the input size n increases - O(1) is a flat line, O(log n) rises very slowly, O(n) is a straight rising line, O(n log n) rises a little faster than O(n), O(n squared) curves steeply upwards, and O(2 to the power n) shoots up almost vertically after a few items There is also an easy way to remember all this. Ask - what happens to the work when the input is doubled? What happens to the work when the input size n is doubled - O of 1 stays the same, O of log n adds just one step, O of n doubles, O of n log n a little more than doubles, O of n squared becomes four times as large, and O of 2 to the power n is squared, which is the reason exponential algorithms are only usable for very small inputs

Finding the Big-O of Your Own Code

To find the Big-O of any method, count its steps as a function of n, and apply the following four rules -
  1. Steps one after the other are added. A loop of n steps followed by another loop of n steps is n + n = 2n steps.
  2. Steps inside steps are multiplied. A loop of n iterations inside a loop of n iterations is n × n steps. A loop of n iterations with a halving loop inside is n × log n.
  3. Drop the constants. 2n is O(n).
  4. Keep only the fastest growing term. n2 + n is O(n2).
A few habits help in practice. A loop whose counter goes up by 1 until n is O(n). A loop whose counter is halved or doubled every time is O(log n). Recursion which makes one call on half of the input is O(log n), and recursion which makes two calls on almost all of the input is O(2n).

Practice Questions

Now it is your turn. Here are four methods which count their steps. Before you look at the output or the answers, decide the Big-O of each one using the rules above.
Four methods - what is the Big-O of each?
package com.javabrahman.algorithms.bigo;
public class QuizCheck {
  static long question1(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 10; j++) {
        steps++;
      }
    }
    return steps;
  }
  static long question2(int n) {
    long steps = 0;
    for (int i = 1; i < n; i = i * 2) {
      for (int j = 0; j < n; j++) {
        steps++;
      }
    }
    return steps;
  }
  static long question3(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < i; j++) {
        steps++;
      }
    }
    return steps;
  }
  static long question4(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          steps++;
        }
      }
    }
    return steps;
  }
  public static void main(String[] args) {
    System.out.printf("%10s %14s %14s %24s%n", "question", "steps, n=100", "steps, n=200", "steps(200) / steps(100)");
    System.out.printf("%10d %14d %14d %24.2f%n", 1, question1(100), question1(200), (double) question1(200) / question1(100));
    System.out.printf("%10d %14d %14d %24.2f%n", 2, question2(100), question2(200), (double) question2(200) / question2(100));
    System.out.printf("%10d %14d %14d %24.2f%n", 3, question3(100), question3(200), (double) question3(200) / question3(100));
    System.out.printf("%10d %14d %14d %24.2f%n", 4, question4(100), question4(200), (double) question4(200) / question4(100));
  }
}
The program runs every method for n = 100 and again for n = 200, and divides the two step counts. This is the doubling test from the previous section - the ratio tells the complexity.  OUTPUT of the above code
  question   steps, n=100   steps, n=200  steps(200) / steps(100)
         1           1000           2000                     2.00
         2            700           1600                     2.29
         3           4950          19900                     4.02
         4        1000000        8000000                     8.00
The answers -
  • Question 1 is O(n). The inner loop always runs 10 times, which is a constant, so the steps are 10n. When n is doubled the work doubles - the ratio is 2.00.
  • Question 2 is O(n log n). The outer loop doubles i every time, so it runs log n times, and the inner loop runs n times for each of those. The ratio, 2.29, is a little more than 2, which is the sign of n log n.
  • Question 3 is O(n2). The inner loop runs i times, so the steps are 0 + 1 + 2 + ... + (n-1), which is n(n-1)/2. This is smaller than n2, but the n2 term still decides the growth, and the 1/2 is a constant. The ratio, 4.02, is almost exactly 4.
  • Question 4 is O(n3). Three loops inside each other multiply to n × n × n. Doubling n makes the work 8 times as large - the ratio is 8.00.
If you got question 3 wrong, you are in good company - it is the one which most students get wrong the first time. The loop does not run n times each time, but the shape of the growth is the same as that of a full nested loop.

Choosing Between Two Solutions

This is the reason Big-O notation exists - to choose between two ways of solving the same problem before writing a line of the final code. Lets take the problem of finding out whether a list of numbers has a duplicate.
  • The nested loops way compares every item with every item after it. This is O(n2).
  • The HashSet way goes through the list once and adds each item to a HashSet. If an item is already in the set, it is a duplicate. Adding to a HashSet and searching in it take O(1) steps on average, so the whole way is O(n).
The program below counts the operations of both ways on lists without any duplicate - the worst case, in which the whole list has to be gone through. It then times the nested loops way. Every size is timed 3 times and the shortest time is taken, so that the effect of the JVM warming up is kept out.
Two ways to find duplicates
package com.javabrahman.algorithms.bigo;
import java.util.HashSet;
public class DuplicateCheck {
  static long operations;
  static boolean hasDuplicateQuadratic(int[] values) {
    for (int i = 0; i < values.length; i++) {
      for (int j = i + 1; j < values.length; j++) {
        operations++;
        if (values[i] == values[j]) {
          return true;
        }
      }
    }
    return false;
  }
  static boolean hasDuplicateLinear(int[] values) {
    HashSet<Integer> seen = new HashSet<>();
    for (int value : values) {
      operations++;
      if (!seen.add(value)) {
        return true;
      }
    }
    return false;
  }
  static int[] distinctValues(int n) {
    int[] values = new int[n];
    for (int i = 0; i < n; i++) {
      values[i] = i;
    }
    return values;
  }
  static double bestMillis(int n) {
    int[] values = distinctValues(n);
    double best = Double.MAX_VALUE;
    for (int run = 0; run < 3; run++) {
      long start = System.nanoTime();
      hasDuplicateQuadratic(values);
      best = Math.min(best, (System.nanoTime() - start) / 1_000_000.0);
    }
    return best;
  }
  public static void main(String args[]) {
    System.out.println("Number of operations when the list has no duplicates (the worst case)");
    System.out.printf("%8s %22s %22s%n", "n", "nested loops: compares", "HashSet: add() calls");
    for (int n : new int[] { 1000, 2000, 4000, 8000 }) {
      int[] values = distinctValues(n);
      operations = 0;
      hasDuplicateQuadratic(values);
      long nested = operations;
      operations = 0;
      hasDuplicateLinear(values);
      System.out.printf("%8d %22d %22d%n", n, nested, operations);
    }
    System.out.println();
    System.out.println("Time taken by the nested loops (best of 3 runs)");
    bestMillis(20000);
    double previous = 0;
    for (int n : new int[] { 10000, 20000, 40000, 80000 }) {
      double time = bestMillis(n);
      System.out.printf("n = %,7d  time = %7.1f ms  %s%n", n, time, previous == 0 ? "" : String.format("(%.1f times the previous)", time / previous));
      previous = time;
    }
  }
}
 OUTPUT of the above code
Number of operations when the list has no duplicates (the worst case)
       n nested loops: compares   HashSet: add() calls
    1000                 499500                   1000
    2000                1999000                   2000
    4000                7998000                   4000
    8000               31996000                   8000

Time taken by the nested loops (best of 3 runs)
n =  10,000  time =    18.8 ms
n =  20,000  time =    74.7 ms  (4.0 times the previous)
n =  40,000  time =   299.0 ms  (4.0 times the previous)
n =  80,000  time =  1193.3 ms  (4.0 times the previous)
Compare the two columns of the first table. For the nested loops, a list of 1000 items needs 499,500 comparisons - this is n(n-1)/2 again, the same sum as in question 3. Every time n doubles, the comparisons become about four times as many. For the HashSet way, the number of add() calls is exactly n, and just doubles when n doubles. This is O(n2) against O(n), in numbers. The timings of the nested loops show the same thing in real time - every doubling of n makes the run about 4 times as long. The exact times will be different on your computer, but the ratio of about 4 will be the same. That is the information which Big-O notation gives you, and which a single measurement of seconds does not. One word of caution. Big-O counts steps, and not all steps cost the same - one HashSet step does much more work than comparing two numbers. For a list of 20 items, the nested loops may even be faster. Big-O tells you which way wins as the list grows.

Best Case, Average Case and Worst Case

The steps of an algorithm can depend on the input itself and not just on its size. Searching for a value in an unsorted list is an example. If the value is the first item, one comparison is enough. If it is the last item, or not in the list at all, all n items must be compared. So there are three cases -
  • Best case - the luckiest input. For the search it is O(1), when the value is the first item.
  • Average case - the typical input. For the search the value is on average in the middle of the list, about n/2 comparisons, i.e. O(n).
  • Worst case - the unluckiest input. For the search it is O(n).
When a complexity is stated without saying which case it is, it is the worst case. Some algorithms have very different cases. Quick SortClick to read tutorial: Quick Sort in Java is O(n log n) on average but O(n2) in its worst case, which happens when the pivot is always the smallest or the largest item. Merge SortClick to read: Merge Sort and Heap SortClick to read tutorial: Heap Sort in Java are O(n log n) in every case, which is why they are chosen when a guaranteed time is needed.

Space Complexity

Big-O notation is used for the extra memory an algorithm needs as well, which is called its space complexity. The memory taken by the input itself is not counted.
  • O(1) extra space - a fixed number of variables, whatever the size of the input. Sorting algorithms which swap items inside the list, such as Bubble, Selection and Insertion Sort, need O(1) extra space.
  • O(n) extra space - memory in proportion to the input. Merge Sort creates new lists for the halves, and the HashSet way of finding duplicates stores up to n items.
  • O(k) extra space - memory which depends on the range of the values, and not on the number of items. Counting SortClick to read tutorial: Counting Sort in Java keeps a count array with one position for every possible value.
  • The call stack counts. A recursive method which goes n levels deep uses O(n) space for its calls, even if it creates no data structure.
Time and space are often traded against each other. The HashSet way is faster than the nested loops because it spends O(n) extra memory, where the nested loops spend none.

What Big-O Notation Does Not Tell You

  • The actual time. An O(n) algorithm with a large constant can be slower than an O(n2) algorithm with a small one for small inputs, because the constants were thrown away. This is why some sorting methods switch to Insertion Sort for very short lists.
  • The cost of a single step. Reading a value which is already in the processor's cache is much cheaper than going to the main memory, but Big-O counts both as one step.
  • More than "on average" for hashing. The O(1) of a HashSet or a HashMap is an average. It depends on the items being spread well over the buckets, and so on the hashCode() method of the items.
Even so, it is the first question to ask about any algorithm - what happens when the input becomes a hundred or a thousand times larger?

Summary

In this tutorial on Big-O notation in java we started with the question of how the work of a task grows when its input grows, saw why steps are counted and not seconds, derived the two simplifications - drop the constants and keep only the fastest growing term - and then met the formal definition with a constant c and a starting point n0, which we checked with a real program. We went through the complexities from O(1) to O(2n) with Java methods which count their own steps, learnt the four rules for finding the Big-O of our own code and practised them on four questions with the doubling test, compared two ways of finding duplicates by counts and timings, and finally understood best, average and worst case, space complexity, and what Big-O notation does not tell.