As we know the running time of an algorithm can depend on various factors such as the architecture of the computer (32 or 64-bit), single or multiple processors, read and write speed, configuration of the machine, input etc.

But for simplicity, we are just going to take input as a variable and keep the rest of the factors constant. Basically, we are going to assume our machine to have the following features:

(Single Processor, 32 bits, sequential execution, takes 1 unit of time for arithmetic and logical operations).

Let’s define a function T(n) as the runtime of a program as a function of the input.

Here are some operations for which T(n)=1

• Assignment operator/ return statement  (Eg: int a=10).
• Arithmetic operations (Eg: + , - , * , / ).
• Logical operations ( Eg: & , | , ^).

Example: 

sum(list,size of list):			
total=0					—->T(n)=1
for i->0 to size of list		—->T(n)=n+1
total+=list[i]			—->T(n)=n
return total			 	—->T(n)=1

Therefore the total runtime of the above program is T(n)=1+2(n+1)+2n+1=4n+4  (Linear)

Similarly, if we have to find the sum of a matrix then the runtime would be quadratic.

Let us take one more example.

bool Find_One(arr[],int n)
{
   for (int i=0; i < n ; i++)
      if ( arr[i] == 1)
      {
     return true;
      }
   return false;
} 

Is it possible to find the running time of the above algorithm without knowing the arr[]?

We can only measure the best and the worst running time of the above algorithm.

In the best case, the running time of the above algorithm would be constant ( the first element of the array itself is 1), whereas in the worst case the running time of the above algorithm would be linear ( there is no 1 in the array ).  

In the next lessons, we are going to see how to do best case and worst case analysis in more detail.