Time Complexity

The time complexity of an algorithm is the amount of computer time it needs to execute and produce the result.

The time T(p) taken by a program P is the sum of the compile time and the run time(execution time). The compile time does not depend on the instance characteristics. Also we may assume that a compiled program will be run several times without recompilation. This rum time is denoted by tp(instance characteristics).

The number of steps any problem statemn t is assigned depends on the kind of statement.

For example,
comments - 0 steps.
Assignment statements - 1 steps [Which does not involve any calls to other algorithms].
Interactive statement such as for, while & repeat-until statements, we consider the step counts only for the control part of the statement.

We can determine the number of steps needed by a program to solve a particular problem instance in one of two ways.

Step count

1. We introduce a variable, count into the program statement to increment count with initial value 0.Statement to increment count by the appropriate amount are introduced into the program. This is done so that each time a statement in the original program is executes count is incremented by the step count of that statement.

Algorithm sum(A,n)
{
	s:= 0.0;
	count := count+1; // count is global; it is initially zero
	for i:=1 to n do
	{
		count := count+1; //for for loop
		s:=s+A[i];
		count=count+1;  //for assignment
	}
	count=count+1;  //for last time of for
	count=count+1;  //for the return
	return s;
}

If the count is zero to start with, then it will be 2n+3 on termination. So each invocation of sum execute a total of 2n+3 steps.

Algorithm Rsum(A,n)
{
	count := count+1;      //for if condition
	if(n ≤ 0) then
	    count := count+1;   //for return
	    retrun 0;
	else
	    count := count+1;   //for return
	    return Rsum(A,n-1)+A[n];
}

$$t_{\mathrm{Rsum}}(n_{})=\{\begin{array}{ll}2& if{n}_{}=0\\ 2\mathrm{+}& t_{\mathrm{Rsum}\left(\mathrm{n-1}\right)}if{n}_{}>0\end{array}$$

Recursive formulas are referred to as Recurrence relations
To solve this, make repeated substitutions.

$$=2+t_{\mathrm{Rsum}}\left(\mathrm{n-1}\right)$$ $$=2+2+t_{\mathrm{Rsum}}\left(\mathrm{n-2}\right)$$ $$=4+2+t_{\mathrm{Rsum}}\left(\mathrm{n-3}\right)$$

$$=n\left(2\right)+t_{\mathrm{Rsum}}\left(0\right)$$
$$=\mathrm{2n}+2$$

Frequency Count Method

2. The second method to determine the step count of an algorithm is to build a table in which we list the total number of steps contributes by each statement.

First determine the number of steps per execution(s/e) of the statement and the total number of times (ie., frequency) each statement is executed. By combining these two quantities, the total contribution of all statements, the step count for the entire algorithm is obtained.

1. Algorithm Sum(a,n)
2.{
3.	s:=0.0;
4.  for i:=1 to n do
5.		s:=s+a[i];
6.  return s;
7.}

0

0

1

1

1

1

0

-

-

1

n+1

n

1

-

0

0

1

n+1

n

1

0

1. Algorithm Rsum(A,n)
2. {
3.	if(n ≤ 0) then
4.	    retrun 0;
5.	else
6.	    return Rsum(A,n-1)+A[n];
7. }

0

0

1

1

0

1+x

0

-

-

1

1

-

0

-

-

-

1

0

-

1

-

0

0

1

1

0

0

0

0

0

1

0

0

1+x

0

$$\mathrm{x}=t_{\mathrm{Rsum}}\left(\mathrm{n-1}\right)$$