Explaining the Big O Notation

The Big O notation is a term used in Computer Science to describe the efficiency or complexity of an algorithm. When you read the Wikipedia article on the concept, chances are that it made very little sense.

Well how about this: Lets say for example you are searching something in Google like “C++ tutorials” or “C++ Books”, then you click the search button and you need to wait about a minute or less before all the results show on the page. Would you still use Google or would you use another search engine that does the job quicker. Chances are that you would use another search engine.

Speed of software today is a major priority today. Slow running software is frustrating to users even if they are using free open source software. Being able to understand how fast an algorithm is performing is the stepping stone to improving them and making software run faster.

The key to understanding how fast an algorithm is calculated is with the labels that come with The Big O Notation.

Operations per Element: This means how much long will your algorithm take to complete as the size of the system grows.

Examples

O(1)

O(1) describes an algorithm that will always be executed in the same time, regardless of the size of the input data.

</pre>
<pre>bool IsElementNull(IList<string> elements)
{
    return elements[0] == null;
}</pre>
<pre>

O(N2)

O(N2) describes an algorithm whose performance is directly proportional to the square of the size of the input data. A common practice of this would involve nested interations over the data set.

</pre>
<pre>bool ContainsValues(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}</pre>
<pre>

What are all of the Big O Notations

There are many of them but to keep things clear and simple, here are the popular ones

Speed Notation Name Practical Example
Fastest O(1) Constant Determining if a number is even or odd; using a constant-size lookup table
O(log n) Logarithmic Finding an item in a sorted array with a binary search
O(n) Linear Finding an item in an unsorted list
O(n2) Quadratic Bubble Sort (worst case or naive implementation)
Slowest O(n!) Factorial Solving the traveling salesman problem via brute-force search
Share this post