C++ Data Structures and Algorithms

Asymptotic analysis

Let's start with asymptotic analysis to find out the time complexity of the algorithms. This analysis omits the constants and the least significant parts. Suppose we have a function that will print a number from 0 to n. The following is the code for the function:

void Looping(int n){    int i = 0;    while(i < n)    {        cout << i << endl;        i = i + 1;    }}

Now, let's calculate the time complexity of the preceding algorithm by counting each instruction of the function. We start with the first statement:

int i = 0;

The preceding statement is only executed once in the function, so its value is 1. The following is the code snippet of the rest statements in the Looping() function:

while(i < n){    cout << i << endl;    i = i + 1;}

The comparison ...