Time
In math, time can be defined as an ongoing and continuous sequence of events that occur in succession, from past through present, and to the future.
What is Time Complexity?
In programming, time complexity measures the amount of time taken to execute each block of code in an algorithm. Complexity of an algorithm is the amount of resources required to run it.
You can get the time complexity by counting the number of operations performed by your code. This time complexity is defined as a function of the input size n using Big-O notation.
Big-O Notation
Big-O notation is a way to describe the speed or complexity of a given algorithm. It tells you the number of operations an algorithm will make.
n is the input size, and O is the worst-case scenario growth rate function.
0(1) — Constant Time
an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
In this example, the result will always be a single number. Here the result would be 25.
0(log n) — Logarithmic Time
an algorithm which as the input size grows, the number of operations grows very slowly.
Here the value of n is halved on each iteration of the loop. As the value of n gets bigger, so will the number of times the function loops.
0(n) — Linear Time
an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
In this example we are looking for the maximum and minimum value of a given list. As the size of the list increases, it will have more values to iterate over to find the max and min of the whole list.
0(n²) — Quadratic Time
an algorithm whose performance is directly proportional to the square of the size of the input data set.
A bubble sorting function is an example of 0(n²). Elements of a list are checked and swapped if they are in wrong order and this process is repeated until we get a sorted list.
0(2ⁿ) — Exponential Time
an algorithm whose growth doubles with each addition to the input data set.
Here we are looking for subsets of a given list s, with a length n. The result would be:
In closing…
The use of time complexity makes it easy to estimate the running time of a program. The lesser the time complexity, the faster the execution.