3 - Time complexity

Time complexity

By calculating the time complexity, we can find out wheter the algorighm is fast enough without implementating it

Calculation rules

The time complexity of an algorithm is denoted O(...) where the three dots represent some function.
Usally, the variable n denotes the input size. For example, if the input is an array of numbers, n will ve the size of the array, and if the input is a string, n will be the length of the string

Loops
The more nested loops the algorithm contains, the slower it is.
For example, the time complexity of the following code is O(n)

for ( int i=1 ; i<=n ; i++) {
	//code
}

And the time complexity of the following code is O(n^2)

for (int i=1; i<=n ;i++){
	for(int j=1; j<=n; j++){
    	//code
    }
}

Phases

If the algorithm consists of consecutive phases, the total time complexity is the largest time compleity of a single phase

Several virable

Sometimes the time complecity depends on several factors 
In this case, the time complexity formula contains several variables
O(mn)

for (int i =1; i<=n; i++) {
	for(int j=1; j<=m;j++){
    	//code
    }
}

Recursion

The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call. The total time complexity is the product of these values
The call f(n) causes n function callse, and the time complexity of each call is O(1) Thus the time complexity is O(n)

void g(int n) {
	if(n==1) return;
    g(n-1);
    g(n-1);
}

In this case O(2^n) 

The following list contains common time complexities of algorithms:

O(1) The running time of a constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer. 

O(logn) A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because log2n equals the number of times n must be divided by 2 to get 1. 

O(rootn) A square root algorithm is slower than O(logn) but faster than 

O(n). A special property of square roots is thatpn=n/pn, so the square rootpn lies, in some sense, in the middle of the input. O(n) Alinearalgorithmgoesthroughtheinputaconstantnumberoftimes. This is often the best possible time complexity, because it is usually necessary to access each input element at least once before reporting the answer. 

O(nlogn) Thistimecomplexityoftenindicatesthatthealgorithmsortstheinput, because the time complexity of efficient sorting algorithms is O(nlogn). Another possibility is that the algorithm uses a data structure where each operation takes O(logn) time. 

O(n2) A quadratic algorithm often contains two nested loops. It is possible to go through all pairs of the input elements in O(n2) time.

O(n3) A cubic algorithm often contains three nested loops. It is possible to go through all triplets of the input elements in O(n3) time.

O(2^n) This time complexity often indicates that the algorithm iterates through all subsets of the input elements. For example, the subsets of {1,2,3} are;, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}.

O(n!) This time complexity often indicates that the algorithm iterates through all permutations of the input elements. For example, the permutations of {1,2,3} are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) and (3,2,1).

Estimating efficiency

The starting point for estimations is the fact that the a modern computer can perform some hunderds of millions of operations in a second.

On the other hand, given the input size, we can try to guess the required time complexity of the algorithm tah solves the problem.
The folloewing table contains some useful estimates assuming a time limit of one second

Maximum subarray sum

There are often several possible algorithms for solving a problem such that their time complexities are different. This section discusses a classic problem that has a straightforward O(n^3) solution. However, by designing a better algorithm, it is possible to solve the problem in O(n^2) times and even in O(n) time.
Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e. the largest possibe sum of a sequence of consecutive values in the array The problem is interesting when there may be negatibe values in the array

Algorithm 1
O(n^3)

int best=0;
for(int a=0;a<n;a++){
	for(int b=a;b<n;b++){
    	int sum=0;
        for(k=a;k<=b;k++){
        	sum += array[k];
    	}
    best = max(best,sum);
	}
}
cout<<best<<"\n";

Algorithm 2
O(n^2)

int best=0;
for(int a=0;a<n;a++){
	int sum=0;
    for(int b=a;b<n;b++){
    	sum+=array[b];
        best=max(best,sum);
    }
}
cout<<best<<"\n";

Algorithm 3
O(n)

int best=0, sum=0;
for(int k=0;k<n;k++){
	sum = max(array[k],sum+array[k]);
    best = max(best,sum);
}
cout<<best<<"\n";

Efficiency comparison