What is running time?

The application has a feature called running time. It is one of the parameters for measuring its performance. It is written in a particular language and is designed to perform a specific task. Applications run in a specific environment. The execution of the business will depend on the application’s running time. It must be optimized in order to get the maximum benefits out of the application.

Calculation of running time

The time complexity of an application is used for calculating or denoting the maximum time that is taken by the algorithm used in the application to produce the desired output. The time complexity of algorithms is generally denoted by the big O notation. It is one of the asymptotic notations used to represent the time complexity. The straightforward method for determining time complexity is to count the number of times each of the algorithm’s operations is executed. But this approach is difficult and unnecessary. The other possibility is to identify the most important operation of the algorithm called basic operation. It is the operation that takes the maximum share of the total running time. The time complexity can be easily determined by actually calculating the number of times the basic operation has been executed. 

So, the steps are as follows:

1. Identify the basic operation, which is the one that executes the maximum times.

2. Calculate the greatest number of times the basic operation gets executed.

Recognizing the most time-consuming basic operation is easy. It is actually the most time-consuming operation in the inner-most loop,

Take an example of an insertion sort algorithm.

Consider applying insertion sort on an array a[8] = {4,3,2,10,12,1,5,6}. The pseudocode of the algorithm is given below:

INSERTION-SORT(A) 

1. for c = 1 to n do 
2. key ← A [c] 
3. q ← c – 1 
4. while q > = 0 and A[q] > key do 
5. A[q+1] ← A[q] 
6. q ← q – 1 
7. End while 
8. A[q+1] ← key 
9. End for

As you can see, the most time-consuming operation in this algorithm is in the innermost loop. It is inside the while loop, which is the key comparison A[q] > key. The maximum number of comparisons made depends on the nature of the input. In worst case, say for an array a[8] = {55,40,37,32,31,27,23,21}, the key comparison A[q] > key is executed the most number of times that is for every q = c-1,....,0 . Therefore, for the worst-case input of an array having strictly decreasing values, the number of key comparisons equals Cworst(n) = O(n^2). The best case input corresponds to an already sorted array, say for an array a[4] = {1,2,3,4}, the comparison A[q] > key is executed only once for every iteration of the outer loop. Therefore, for the best case input of strictly increasing values, the number of key comparisons equals Cbest(n) = O(n).

Asymptotic analysis

The asymptotic notations that are used to represent the time complexity or simply the running time of an algorithm are as follows.

1. Big- O notation: This notation is used to describe the maximum running time of an algorithm. It denotes the upper bound, that is, it denotes the maximum time that an algorithm will take. 
2. Omega Notation: It is used to represent the minimum running time of an algorithm. It denotes the lower bound, that is, it is used to describe the minimum time an algorithm will take.
3. Theta Notation: It is used to represent the range in which an algorithm's time complexity falls. It is used to describe both the upper and lower bound for running time of an algorithm.

Types of Time Complexities

The time complexity of the algorithms used in an application falls into any of the following categories:

1. O(1) - Constant time: When an algorithm takes the same amount of time to give an output even when the input sizes vary, then it is said to have a constant time complexity. 
2. O(n) - Linear time: When an algorithm takes time which varies as the input size varies. If the time complexity increases linearly with the input size, then it falls under this category.
3. O(n^2) - Quadratic time: When an algorithm faces a quadratic increase in the total running time as the input size increases, then it is said to have quadratic time complexity.
4. O(n^c) - Polynomial time: When an algorithm’s running time is bounded by a polynomial, then it is said to have polynomial time complexity.
5. O(log n) - Logarithmic time: When the running time of an algorithm grows logarithmically as the input size grows, then it is said to have logarithmic time complexity.
6. O(2^n) - Exponential time: When for an algorithm the running time doubles with increase in the size of input, then it is said to have exponential time complexity.

Running Time Analysis of Algorithms

1. Worst case analysis: It is used to calculate the time required by the algorithm in the worst case. The worst case of an algorithm is determined by giving the input that it will take maximum time for the algorithm to solve the problem and produce the result. For example, in case of a searching algorithm, which searches the element in an array linearly, the worst case is when the element is not present in the array. This results in the algorithm to search all the elements in the array and thus, taking the maximum time.
2. Best case analysis: It is used to calculate the time required by an algorithm in the best case. The best case of an algorithm is when the input given to the algorithm is in such a way that it takes the minimum amount of time for the algorithm to produce results. For example, in the case of a searching algorithm, which searches an element linearly, the best case is when the element to be searched is present at the first position in the array.
3. Average case analysis: It is used to describe the time taken by the algorithm on an average. This can be done by taking a wide variety of inputs and calculating the running time of the algorithm for each of the inputs. Then, an average of the values obtained is computed.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for, bachelor's in computer science engineering, and an associate of science in computer science.

Practice Problems

Question 1: Running time is determined by counting the number of times the _______ operation is executed.

1. basic
2. addition
3. subtraction
4. division

Answer: Option a is correct.

Explanation: Running time is determined by counting the number of times the basic operation is executed.

Question 2: If the time complexity increases linearly with the input size, then its time complexity belongs to the class ________

1. O(n^2)
2. O(log n)
3. O(1)
4. O(n)

Answer: Option d is correct.

Explanation: Linear complexity is given by O(n).

Question 3: When the time complexity doubles with respect to the size of input then the algorithm's time complexity belongs to _____________ class.

1. Polynomial
2. Quadratic
3. Exponential
4. Cubic

Answer: Option c is correct.

Explanation: If the growth gets doubled with the input size, then it is referred to as exponential.

Question 4: What are three asymptotic notations?

1. alpha, gamma and delta
2. big-oh, omega, and theta
3. omega, theta, and delta
4. alpha, omega, and delta

Answer: Option b is correct.

Explanation: Big-oh, omega, and theta are the notations used to represent the time complexity.

Question 5: Which notation is used to represent the lower bound on the time complexity of an algorithm?

1. big-oh
2. omega
3. theta
4. None of the above

Answer: Option b is correct.

Explanation: Omega is used to represent the lower bound on the time complexity of the algorithm.