Trivial Runtime Analysis

In this lesson, you'll learn how to determine the run-time complexity of a given piece of code through some samples.

We'll cover the following

Big-O

The goal of code analysis is to determine its run-time complexity with growing input size NN.

If there is no input, then it’s called a constant time algorithm. For example:

for (int i = 0; i < 1000000; i ++)
      x++;

How many times does the statement x++ gets executed? A million times. But it’s fixed or constant, so it’s always a million operations no matter what. So the time complexity is O(1)O(1) (constant time).

Some properties of Big-O notation:

  • O(c)O(c) is O(1)O(1), where c is any constant
  • O(cN)O(cN) is O(N)O(N)
  • O(N2+N)O(N^2 + N) is O(N2)O(N^2), we only consider highest order term
  • O(N+c)O(N + c) is O(N)O(N)
  • O(Nc)O(N - c) is O(N)O(N)

We hide the constant when expressing the algorithm’s runtime complexity using Big-O. Sometimes this hidden constant becomes relevant as a big hidden constant will affect the actual execution time of the code. This will become more evident as we learn algorithms that affect and/or are affected by the hidden constants.

Basic loops

Let’s go through some code samples and analyze their runtime complexity.

for (int i = 0; i < N; i ++)
      x++;

All we need to do is count the number of times the statement x++ will execute. Clearly, it’s NN, so the time complexity is $O(N), also called linear.

for (int i = 0; i < N; i++) 
    for (int j = 0; j < i; j++) 
        x++;

How many times the statement x++ executes:

  • When i=0i=0, 00 times
  • When i=1i=1, 11 time
  • When i=2i=2, 22 times and so on

This turns out to be 0+1+2+3+..+N1=N×(N1)20 + 1 + 2 + 3 + .. + N-1 = \frac{N \times (N-1)}{2}

So the time complexity is O(N2)O(N^2), also called quadratic.


In the next lesson, we’ll analyze logarithmic run-time cases.