dimanche 17 janvier 2021

Understanding Complexity (Urban Traffic VS Highway Traffic)

Sometimes, algorithmic complexity, when approached academically, or mathematically, might go astray its literal meaning.

Indeed, algorithmic complexity is described using theoretic mathematical expressions, and referred to basically by using Big O notation.

As a matter of fact, algorithmic complexity has a picturesque meaning.
 
Indeed, sometimes a bad algorithm is the one that has a pointless high complexity, and any experienced programmer can easily find for optimisation.

Reducing complexity can sometimes mean that an unnecessary recalculation is repeatedly done. Sometimes, a value needs to be calculated only by using a formula rather than using (nested) loops etc.

A real life situation is traffic in the city versus traffic in the highway.

The distance between home and downtown is 10 km, but it takes me 45 minutes to reach my destionation, taking into account traffic lights, intersections, the tramway ...

Whereas, the distance between home and a former job located in a suburban area is 20 km, it takes me 20 minutes only to get there using the highway.

As a deduction, complexity is very high in the city with upper bound (business days) and lower bound (holidays / weekend): small o notation.

While complexity is very low (big o notation where lower bound is equal upper bound).

Some techniques are used to exploit space complexity for the benefit of time complexity.
The structure below (example) is used to connect two neighbourhoods separated by railways :
In Rabat, a section of the highway has become an inherent part of the city. Therefore, travellers needed to reduce speed, and stop at traffic lights or at stop signs. But, during the last decade, there were ongoing projects to establish underground tunnels so that travellers wouldn't have to stop, and speed limit was raised from 60 km/h to 80 km/h. 
 
Indeed, establishing tunnels reduced considerably time complexity in this section of the highway.

In summary, the discussion above allows to have a concrete situation of what complexity can be, with the intention of simplifying the understanding of the algorithmic complexity, and its purpose in general.