Basic run-time analysis

A different kind of running (Photo: Pixabay CC0)

Run-time analysis sounds technical, but it is key to succeeding in programming, even if you are planning a career in pure front end and feel nervous shivers at the bare mention of the word algorithm.

So why should you care about “run-time analysis”? Run-time analysis can save you from writing slow programs and it will help you understand why some algorithms are better than others.

When I talk about slow here, what I mean is that your code should be reasonably fast for any realistic inputs — anyone can write a fast program that works on small inputs (think sorting 10 numbers), but it is a bit more difficult to sort 1 billion, without waiting for the sun to die (possible though :)

In this article I will show a very basic, non-formal analysis of two very simple programs. Then in the next article I will continue with two sorting algorithms (selection sort and merge sort).

Analyzing my first program

Let us look at the following program:

Func printNumbers(list : List<Integer>)
  For i <= 0, i<list.length, i <= i+1
    printline(list[i])
  End
End func

The program takes a list of integers as its argument and prints each of them in turn on a new line. How long will this take is a reasonable question. We could try to answer this by looking at some chosen inputs, for example 10 items, 100 and a 1000 and measure how long it takes. We are usually not so interested in the exact amount of time, but rather we would like to know, if the input grew to, for example, double size, how much longer would it take to run the program? To answer this question, we need to take a small detour, then we are getting back to printNumbers and in the end we are going to take a look at some algorithms that are a bit tougher.

It’s all about size…

You may have been told that it’s not — but newsflash: size does matter, at least in this case. The size I am talking about is of course input size. In the world of run-time analysis, we are usually referring to the mythical n, which refers to the size of input in whatever unit is convenient, it could be characters, numbers in an array or something else, it is not important as you will see shortly.

Big O notation

I am sorry for the innuendos, but it is really called that. I am not going to go into the mathematical definition, but you can think of it as a kind of rounding for functions, for example: O(2^n +7)=O(2^n) or O(n²+n)= O(n²)

The point is that the part that contributes most to growth is kept and the rest goes away.

Getting back to analyzing printNumbers

If we want to understand how the runtime of printNumbers grows with increasing input sizes, we have to look at the additional code that will be run when n(the size of the input) grows by 1.

Two things are then going to happen:

1. A jump from the end of the for loop to the beginning.
2. Some kind of print routine is going to be invoked, which we assume will take the same amount of time for any number (probably it will take a bit longer for long numbers, but it’s an okay assumption to make for our purposes).

Those two things both take a (more or less) fixed amount of time, so added together they also take a fixed amount of time. What this means is that when n grows by 1, the run time grows by a constant amount, we call this a linear run-time and we say that the algorithm is O(n).

A real world example of linear run-time and how to improve it

Something that most programmers have experienced, one time or the other, is to determine whether a specific value is in a list, for example to see if a certain user is part of a group of users.

The obvious way of deciding if a value is in a list, is to write a program, much like printNumbers, which looks at every single item in the list and returns true if one of them is equal to the value we are looking for, and false if none of them do.

Func containsValue(list : List<Integer>, value : Integer)
  var result : boolean
  result <= false #This is the default state
  For i <= 0, i<list.length, i <= i+1
    if list[i] = value then
      result <= true 
    end if
  End 
  return result
End func

The program containsValue first sets up a variable, result, to contain the result of the function. By default it is false, but if we find a match, we set it to true. Then we return result.

What is big O run time of this algorithm? This time we have to parameters, so what is the input and how to understand its size?

The first input is a list and the second one is a constant, which is not going to change size, so we can ignore that.

For each step in the for loop we do the following:

1. Get the value of position i in the list
2. Compare it with the value value
3. If they are the same, then set the variable result to true, else do nothing.

Each of those operations take a constant amount of time, and since the number of times the for loop runs depends on the length of the list, we again have a linear run-time or O(n).

So now that I have shown you how to analyze very simple algorithms, you are prepared to continue with the next article Continued run-time analysis