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.