How to find Time Complexity of Algorithms | DSA Tutorials

Guide on to find the time complexity of algorithms – It is very easy to classify algorithms based on the relative amount of time or relative amount of space they require, and specify the growth of time/space requirements as a function of the input size. Thus, we have the notions of Time complexity and Space Complexity.

1. Time Complexity: Running time of the program as a function of the size of the input. The running time is the number of primitive operations (steps) executed before termination (completion).
2. Space Complexity: The amount of computer memory required during the program execution, as a function of the input size.

Suppose P is an algorithm, and suppose K is the size of the input data. The time and space used by the algorithm P are the two main measures for the efficiency of P. The time is measured by counting the number of key operations in sorting and searching algorithms, for example, the number of comparisons. That is because key operations are so defined that the time for the other operations is much less than or at most proportional to the time for the key operations. The space is measured by counting the maximum amount of memory needed by the algorithm.

The complexity of an algorithm P is the function f(n), which gives the running time and/or storage space requirement of the algorithm in terms of the size n of the input data. Frequently, the storage space required by an algorithm is simply a multiple of the data size n. Accordingly, unless otherwise stated or implied, the term “complexity” shall refer to the running time of the algorithm.

Measurement of the Time Complexity of Algorithms

The runtime of a program depends on several factors, such as:

1. The time complexity of the algorithm.
2. The input of the program.
3. The quality of the implementation and the quality of the code generated by the compiler.
4. The machine used to execute the program.

We are not interested in developing a theory that is only valid for algorithms implemented by a particular programmer in a particular programming language using a particular compiler and being executed on a particular machine, so we have to abstract from all these factors. We do this in the following way: We describe our algorithms in a pseudo-code that resembles programming languages such as JAVA or C, but is less formal (since it is only intended to be read and understood by humans).

We assume that each instruction of our pseudocode can be executed in a constant amount of time, more precisely, in a constant number of machine cycles that does not depend on the actual values of the variables involved in the statement, no matter in which “real” programming language it is implemented and on which machine it is executed.

Let’s take an example to find the time complexity of the algorithm.

Example 1: Given below is the pseudo-code description of an algorithm that searches for an integer in an array of integers. Compare this with the actual implementation as a Java method displayed below.

Solution:

Algorithm seqSearch (A, k)
Input : An integer array A, an integer k
Output : The smallest index i with A[i] = k, if such an i exists, or -1 otherwise.
1. for i ← 0 to A.length - 1 do
2. if A[i] = k then
3. return i
4. return -1

public static int seqSearch (int [] A, int k)
{
  for (int i = 0; i < A.length; i++)
  if (A[i] == k)
  return 1;
  return -1;
}

Algorithm seqSearch (A, k)
Input : An integer array A, an integer k
Output : The smallest index i with A[i] = k, if such an i exists, or -1 otherwise.
1. for i ← 0 to A.length - 1 do
2. if A[i] = k then
3. return i
4. return -1

public static int seqSearch (int [] A, int k)
{
  for (int i = 0; i < A.length; i++)
  if (A[i] == k)
  return 1;
  return -1;
}

The above program is the implementation of the algorithm in JAVA.

We now want to get an estimate of the runtime of seqSearch when the input consists of the array A (2, 4, 3, 3, 5, 6, 1, 0, 9, 7) and the integer k = 0. The length of 4 is 10, and k occurs with index 7. What we actually estimate is the number of machine cycles an execution of the algorithm requires. More abstractly, instead of machine cycles, we usually speak of computation steps multiplied by the clock speed of our machine. This gives us an estimate of the actual runtime.

Unfortunately, we do not know how many computation steps an execution of Line 1 requires; this number will depend on factors such as the programming language, the compiler, and the instruction set of the CPU, but clearly, for every reasonable implementation on a standard machine, it will only require a small constant number of steps. Here, “constant” means that the number can be bounded by a constant that does not depend on the values of i and A. length. Let c1 be such a constant. Similarly, let us say that Lines 2, 3, 4 require at most c2, c3, and c4 steps.

To compute the number of computation steps executed by Algorithm on input A = {2,4,3,3,5,6,1,0,9,7} and k = 0, we have to find out how often each line is executed: That’s easy. Line 1 is executed 8 times (for the values i = 0,…, 7). Line 2 is also executed 8 times. Line 3 is executed once, and Line 4 is never executed. Thus, overall, at most

8c1 + 8c2 + c3

Computation steps are performed. A similar analysis shows that on input A = {2, 4, 3, 3, 5, 6, 1, 0, 9, 7} and k=10 at most

11c1 + 10c2 + c4

Computation steps are performed. (Line 1 is performed 11 times, the last time to check that 11 >= 10=A. length.)

public class seqSearch
{
public static int seqSearch (int [] A, int k)
{
for (int i = 0; i < A.length; i++)
if (A [i] = = k)
return i;
return -1;
}
public static void main (String [] args)
{
int [] A = {2, 4, 3, 5, 6, 1, 0, 9, 7};
System.out.println(seqSearch (A,0));
System.out.println(seqSearch (A, 10));
}
}

public class seqSearch
{
public static int seqSearch (int [] A, int k)
{
for (int i = 0; i < A.length; i++)
if (A [i] = = k)
return i;
return -1;
}
public static void main (String [] args)
{
int [] A = {2, 4, 3, 5, 6, 1, 0, 9, 7};
System.out.println(seqSearch (A,0));
System.out.println(seqSearch (A, 10));
}
}

In this point of view, we have obtained a weird estimate, involving unknown constants, on the number of computation steps performed by our algorithm on two particular inputs. What we would like to have is an estimate of the number of computation steps performed on arbitrary inputs. But clearly, we cannot just disregard the input; an execution of our algorithm can be expected to perform more computation steps if the input array has length 100,000 than if the input array has length 10.

Therefore, we define the time complexity of the algorithm as a function of the size of the input, which in Example 1 is the length of A. But even for input arrays of the same length, the execution time may vary greatly, depending on where the number we search for appears in the array. We resolve this by giving an estimate of the number of computation steps needed in the worst-case.

The (worst-case) time-complexity of an algorithm A is the function T_A: N $\rightarrow$ N where T_A (n) is the maximum number of computation steps performed by A on an input of size n. Let us analyse the worst-case time complexity of the algorithm seqSearch. It is quite obvious that the worst-case inputs are those where either k only appears as the last entry of A or where k does not appear at all.

Suppose A has length n. If k appears at the last entry, the number of computation steps performed is at most

c1.n + c2.n + c3 = (c1 + c2).n + c3;

And if k does not appear at all, it is

c1.(n + 1) + c2.n + c4 = (c1 + c2).n + (c1 + c4);

Thus, the time complexity of seqSearch is

T_seqSearch (n) ≤ max {(c1+c2). n + c3, (c1 + c2). n + (c1 + c4))
=(c1+c2). n + max (c3, (c1+c4))

Since we do not know the constants c1, c2, c3, and c4, we cannot tell which of the two values is larger. But the important thing we can see from our analysis is that the time complexity of seqSearch is a function of the form

a.n+b;

For some constants a, b. This is a linear function; we say that seqSearch requires linear time.