Understanding time complexity on simple examples - Part 2

So, how can one determine that one method is superior to another?

In reality, there isn't a single definitive answer to this question, as the term "superior" can carry different meanings for each individual. Some may argue that a method is superior if it requires less space in memory, particularly important for devices where memory management is critical, such as microcontrollers. Others may consider a method superior if it is easy to understand and explain. In this series, we will define a method as superior if it simply takes less time to execute than others.

Before we proceed, let's clarify some terminology: a finite set of tasks or instructions processed by a computer to achieve a result in a finite amount of time is informally referred to as an algorithm. Our objective is, therefore, to ascertain, among several algorithms, those that are better suited to terminate earlier. This analysis of the time taken by algorithms to perform a task is known as time complexity and has been crucial since the early days of computer science.

How to measure and compare time complexity ?

Time complexity is thus a measure of the amount of time an algorithm takes to complete based on the size of its input. It provides an estimation of the computational time required for an algorithm to run as a function of the input size. Computer scientists universally employ big O notation to describe time complexity, and our objective in this section is to clarify what this notation signifies.

Informally, what is big O notation ?

Consider the scenario where we are tasked with designing a program that operates on an array of 5 integers (the specifics of the program are irrelevant). Upon implementation, we conduct natural testing and observe that it takes 5 seconds to execute. Subsequently, we modify the input to utilize an array of 10 integers, run the program with these new arguments, and discern that it now takes 10 seconds to execute. From this observation, we can deduce that if we were to double the size of the inputs, the execution time also doubles: the relationship between execution time and inputs is linear.

Now, envision that we delve deeper into the literature and unearth an alternative approach for implementing this program. Equipped with this newfound method, we re-implement the previous algorithm, conduct another round of testing, and note that it now takes 0.5 seconds to execute with 5 integers and 1 second with 10 integers. From this, we can once again infer that if we were to double the size of the inputs, the execution time also doubles: the relationship between execution time and inputs remains linear.

Indeed, at first glance, the second method appears superior as it consumes less time with the same input. However, upon delving into additional research papers, we encounter a new algorithm. While it is somewhat more intricate, it takes 12 seconds to execute with an array of 5 integers and, surprisingly, also 12 seconds with an array of 10 integers. This method seems to be notably less favorable. Not only is it more challenging to implement, but it also requires more time to execute!

With a heightened awareness, we proceed to conduct experiments under real-world conditions using an array of 1000 integers. As anticipated, the first method takes 1000 seconds to execute, while the second method takes 100 seconds. However, quite surprisingly, the third algorithm once again takes only 12 seconds. Now, this third algorithm substantially outperforms the others!

There are several key insights to glean from this example.

• Firstly, the superiority of an algorithm can only be meaningfully studied and compared with asymptotic data, particularly as the input size becomes larger and larger. The third method mentioned earlier runs in constant time, exhibiting consistent performance regardless of input size, whereas the other two exhibit a time complexity proportional to the inputs.
• Secondly, even though the second algorithm may appear to run faster than the first one, this difference becomes less relevant for larger inputs. The crucial consideration is that its time complexity remains linear in relation to the size of the arguments passed.

Informally, we would say that the third algorithm executes in constant time or is an $O(1)$ algorithm. On the other hand, the first and second algorithms execute in linear time and are $O(n)$ algorithms.

In brief, big O notation allows developers and researchers to compare the efficiency of algorithms in a language-independent and platform-independent manner. It focuses on the high-level behavior of algorithms and is particularly useful when analyzing the scalability of algorithms for large input sizes. Keep in mind that while big O notation provides an upper bound, it doesn't capture constant factors, lower-order terms, or specific details of the implementation.

And formally, what is big O notation ?

Let $f$ and $g$ be real valued functions and let both functions be defined on some unbounded subset of the positive integers ($\N$). One writes $f((n)=O(g(n))$ if there exists $k \in \R$ and $n_{0} \in \N$ such that $\vert f(n)\vert \le k\vert g(n)\vert$ for all $n \ge n_{0}$.

In our context, the function $f$ will denote the execution time of an algorithm, and $n$ will represent the number of integers in an array. In the first case, we have $f(n)=n=kn$ with $k=1$, and thus $f(n)=O(n)$ according to the definition. In the second case, we have $f(n)=n/10=kn$ with $k=1/10$, and once again, $f(n)=O(n)$. Regarding the third case, we have $f(n)=12=k*1$ with $k=12$, and so $f(n)=O(1)$.

More information can be found here.

What are the common big O notations ?

Here are some common big O notations:

• $O(1)$ - The time complexity is constant regardless of the input size. These algorithms are generally the best.
• $O(log n)$ - The time complexity grows logarithmically with the input size. These algorithms are highly desired.
• $O(n)$ - The time complexity is directly proportional to the input size.
• $O(nlog n)$ - The time complexity is said to be linearithmic and is common in efficient sorting algorithms like merge sort and quicksort.
• $O(n^2)$ - The time complexity is proportional to the square of the input size (quadratic). It is common in less efficient sorting algorithms.
• $O(2^n)$ - The time complexity is exponential and the running time grows rapidly with the size of the input. These algorithms are generally useless on large inputs and must be avoided.

In the next post, we will explore how to practically apply this notation with simple examples. See you here.