Efficiency or Complexity

An algorithm is, in plain English, just a series of steps for solving a problem.

Solving problems is about creativity, how to approach the problem with a proper solution.

Some solutions may be easy to come up with, but they are not efficient, that is, the complexity is higher than it needs to be.

When I say efficient, you can think about it in two dimensions: space and time.

The time dimension is about how long your solution takes to solve the problem

The space dimension is about how much storage your solution consumes to solve the problem.

In the end, both dimensions combine to one goal: better use of limited resources.

Your computer has some amount of CPU, RAM, and storage, you need to get a job done considering these constraints.

Having a good grasp of algorithms and data structures helps a lot in achieving that.

Choosing the right data structure and the right algorithm helps in saving lots of resources while solving the problem faster.

Big O Notation

Let's say two people write each the same solution for a given problem.

How can you tell which one is better?

For this, you can use the Big O Notation, also known as O(n).

The n stands for the input to your algorithm, to your function.

If you have to do some computation on 10 records, your n is 10, so n is the length of the input.

Of course, if you have to deal with 10 or 1 million records, the same solution might not be optimal for both cases, as you may notice that something that works well with small amounts of data shall not hold with big amounts of data.

The O stands for a mathematical function of the input n, the same way we define the classic f(x) in math.

Approximation

Complexity is often thought of like a worst-case scenario.

This means that, given a problem with 10 records, your program would have to loop over all 10 to find the information you need.

There is also the situation where the first record is the one you want, called the best case, and finally, there is the average case, which would be 5 if we are working with 10 records.

Use approximations and extrapolations when dealing with complexity and Big O Notation.

The cases O(n+2), O(2n+20), O(3n+200) can all be approximated to O(n).

Take this example, every line is a computation as shown in the comments of the code below.

Each line in the for loop count as n because they do computations on the input, thus the complexity in the for block is proportional to the input.

On the other hand, x = 0 and return x count as just 1, they are executed only once.

def myFunction(n):
    x = 0 #1
    for i in n: #n
        y =2*i #n
        x += y #n
    return x #1

print(myFunction([1,2,3]))
#output: 12

Counting the number of n and 1 in the function, the complexity of the example above is O(3n+2).

Some people don't count the line with the for itself, in this case, the complexity would be O(2n+2).

In both cases, regardless, applying the approximation rule, it simplifies to O(n), since constant multiples or simple additions of constants do not matter for the general growth rate of a function.

In this example we have a linear growth rate, that is what matters in the end.

Practical Understanding

I've described the reasons why you should worry about which algorithms and data structure to choose and the notation used as a common language to describe efficiency and complexity.

In this section, let's see some code snippets and calculate their complexity with the Big O Notation.

Example 1: O(1)

The first example refers to a constant growth rate.

Notice that the function firstCar() only prints the properties of the first item/dictionary in the list, just a simple lookup.

Each print command accessing one property counts as one, so we have O(5), and due to the approximation principle, the final complexity for this function is simple O(1).

bmw = {
  "name": "BMW 320i",
  "torque": "550 Nm",
  "year": 2019,
  "top_speed": "280 km",
  "cylinder_capacity": "1998 cc"
}
ferrari = {
  "name": "Ferrari F8",
  "torque": "770 Nm",
  "year": 2020,
  "top_speed": "340 km",
  "cylinder_capacity": "3902 cc"
}
mclaren = {
  "name": "McLaren 720S",
  "torque": "770 Nm",
  "year": 2017,
  "top_speed": "341 km",
  "cylinder_capacity": "3994 cc"
}

cars = [bmw, ferrari, mclaren]

def firstCar(cars):
    print(cars[0]['name']) #1
    print(cars[0]['torque']) #1
    print(cars[0]['year']) #1
    print(cars[0]['top_speed']) #1
    print(cars[0]['cylinder_capacity']) #1

firstCar(cars)
#output:
#BMW 320i
#550 Nm
#2019
#280 km
#1998 cc

Example 2: O(n)

This is the one I discussed before, linear growth rate.

We iterate over each item of the list and print the property name since the iteration is over the n items in the list, it gives us O(n).

bmw = {
  "name": "BMW 320i",
  "torque": "300 Nm",
  "year": 2019,
  "top_speed": "280 km",
  "cylinder_capacity": "1998 cc"
}
ferrari = {
  "name": "Ferrari F8",
  "torque": "770 Nm",
  "year": 2020,
  "top_speed": "340 km",
  "cylinder_capacity": "3902 cc"
}
mclaren = {
  "name": "McLaren 720S",
  "torque": "770 Nm",
  "year": 2017,
  "top_speed": "341 km",
  "cylinder_capacity": "3994 cc"
}

cars = [bmw, ferrari, mclaren]

def carNames(cars):
    for car in cars: #n
        print(car['name'])

carNames(cars)
#output:
#BMW 320i
#Ferrari F8
#McLaren 720S

Example 3: O(nm)

In this code snippet, we have two nested for loops.

The first loop iterates over the items, n, of the list while the second loop iterates over the properties, m, of each item.

So the complexity is the number of items times the number of properties, thus O(nm).

bmw = {
  "name": "BMW 320i",
  "torque": "300 Nm",
  "year": 2019,
  "top_speed": "280 km",
  "cylinder_capacity": "1998 cc"
}
ferrari = {
  "name": "Ferrari F8",
  "torque": "770 Nm",
  "year": 2020,
  "top_speed": "340 km",
  "cylinder_capacity": "3902 cc"
}
mclaren = {
  "name": "McLaren 720S",
  "torque": "770 Nm",
  "year": 2017,
  "top_speed": "341 km",
  "cylinder_capacity": "3994 cc"
}

cars = [bmw, ferrari, mclaren]

def carSpecs(cars):
    for car in cars: #n
        for spec in car: #m
            print(spec, ": ", car[spec])

carSpecs(cars)
#output:
#name :  BMW 320i
#torque :  300 Nm
#year :  2019
#top_speed :  280 km
#cylinder_capacity :  1998 cc
#name :  Ferrari F8
#torque :  770 Nm
#year :  2020
#top_speed :  340 km
#cylinder_capacity :  3902 cc
#name :  McLaren 720S
#torque :  770 Nm
#year :  2017
#top_speed :  341 km
#cylinder_capacity :  3994 cc

Example 4: O(n^2)

Like the last example, we have two nested for loops here, but this time each loop iterates over the same list of items n.

For every car, I compare it to every other car's speed.

The complexity is the number of items in the first loop times the number of items in the second loop, thus O(nn) or simply O(n^2), also known as a quadratic growth rate.

bmw = {
  "name": "BMW 320i",
  "torque": "300 Nm",
  "year": 2019,
  "top_speed": "280 km",
  "cylinder_capacity": "1998 cc"
}
ferrari = {
  "name": "Ferrari F8",
  "torque": "770 Nm",
  "year": 2020,
  "top_speed": "340 km",
  "cylinder_capacity": "3902 cc"
}
mclaren = {
  "name": "McLaren 720S",
  "torque": "770 Nm",
  "year": 2017,
  "top_speed": "341 km",
  "cylinder_capacity": "3994 cc"
}

cars = [bmw, ferrari, mclaren]

def fasterCar(cars):
    faster_car = {}
    for car1 in cars: #n
        for car2 in cars: #n
            if car1['top_speed'] > car2['top_speed']:
                faster_car = car1
            else:
                faster_car = car2
    return faster_car

print(fasterCar(cars))
#{'name': 'McLaren 720S', 'torque': '770 Nm', 'year': 2017, 'top_speed': '341 km', 'cylinder_capacity': '3994 cc'}

Conclusion

This was the first introduction to complexity and the Big O Notation, in future posts discussing different algorithms and data structures I will analyze the many other types of growth rates.

Originally published at https://renanmf.com/4-examples-algorithmic-complexity-big-o-notation/