How does running time get affected when the input size is quite large?

### What is an algorithm?

### Why do you need to evaluate an algorithm?

### Counting number of instructions:

int n=array.length for (int i = 0; i < n; i++) { if(array[i]==elementToBeSearched) return true; } return false;

- For assigning a value to a variable
- For comparing two values
- Multiply or addition
- Return statement

**In the Worst case:**

So :

Hence f(n)=3n+3

if(array[i]==elementToBeSearched) ,i++ and i<n <b>will be executed n times</b> int n=array.length,i=0,return true or false <strong>will be executed one time. </strong>

### Asymptotic behaviour :

- As n grows larger, we can ignore constant 3 as it will be always 3 irrespective of the value of n. It makes sense as you can consider 3 as the initialization constant and different languages may take different times for initialization. So the other function remains f(n)=3n.
- We can ignore constant multiplier as different programming languages may compile the code differently. For example, array lookup may take a different number of instructions in different languages. So what we are left with is f(n)=n

### How will you compare algorithms?

**You can compare algorithms by its rate of growth with input size n**

^{ }+2n+4 and f(n) =4n+4

**For f(n) =4n^2**

^{2 }+2n+4so here

f(1)=4+2+4

f(2)=16+4+4

f(3)=36+6+4

f(4)=64+8+4

….

As you can see here the contribution of n^2

^{2 }increases with an increasing value of n.So for a very large value of n, contribution of n^2 will be 99% of the value on f(n).

n^2+2n+4 ——–>n^2

**For f(n) =4n+4**

so here

f(1)=4+4

f(2)=8+4

f(3)=12+4

f(4)=16+4

….

As you can see here the contribution of n increases with the increasing value of n.So for a very large value of n, the contribution of n will be 99% of the value on f(n).

4n+4 ——–>nSo here n is the highest rate of growth.

**Point to be noted :**

**We are dropping all the terms which are growing slowly and keep one which grows fastest.**

### Big O Notation:

When you say O(g(n)) , It means it will never be worst than g(n).

Having
said that it means O(g(n)) includes smaller or same order of growth as g(n).

So O(n) includes O(n),O(logn) and O(1).

Writing in a form of
f(n)<=c*g(n) with f(n)=4n+3 and g(n)=5n

Writing in a form of
f(n)<=c*g(n) with f(n)=4n+3 and g(n)=6n

so there can be multiple values for n0 and c for which f(n)<=c g(n)
will get satisfied.

Writing in a form of f(n)<=c*g(n) with
f(n)=4n^2^{ }+2n+4 and g(n)=5n^2

4n^2^{ }+2n+4<=5n^2 for n0=4 and c=5

Let's take some examples and calculate a value for c and n0.

**1. f(n)=4n+3**4n+3<=5n for
n0=3 and c=5.

or 4n+3<=6n for n0=2 and c=6

**2. f(n)=4n^2+2n+4**

### Rules of thumb for calculating the complexity of an algorithm:

**Consecutive statements:**

So O(f(n))=1

**Calculating complexity of a simple loop:**

Time complexity of a loop can be determined by running time of statements inside loop multiplied by total number of iterations.

int m=0; // executed in constant time c1 // executed n times for (int i = 0; i < n; i++) { m=m+1; // executed in constant time c2 }

f(n)=c2*n+c1;

So O(n)=n

**Calculating the complexity of a nested loop:**

It is a product of iterations of each loop.

int m=0; executed in constant time c1// Outer loop will be executed n timesfor (int i = 0; i < n; i++) {// Inner loop will be executed n timesfor(int j = 0; j < n; j++){m=m+1; executed in constant time c2}}

f(n)=c2*n*n + c1

So
O(f(n))=n^2

**If and else:**

When you have if and else statement, then time complexity is calculated with whichever of them is larger.

int countOfEven=0;//executed in constant time c1 int countOfOdd=0; //executed in constant time c2 int k=0; //executed in constant time c3 //loop will be executed n times for (int i = 0; i < n; i++) { if(i%2==0) //executed in constant time c4 { countOfEven++; //executed in constant time c5 k=k+1; //executed in constant time c6 } else countOfOdd++; //executed in constant time c7 }

f(n)=c1+c2+c3+(c4+c5+c6)*n

So o(f(n))=n

**Logarithmic complexity**

Now let’s assume our sorted array is:

int[] sortedArray={12,56,74,96,112,114,123,567};

and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iterations you are
cutting the scope of array to the half. In every iteration, we are
the overriding the value of first or last depending on
soretedArray[mid].

So for

0th iteration : n

1th iteration: n/2

2nd
iteration n/4

3rd iteration
n/8.

Generalizing above
equation:

For ith iteration :
n/2^{i}

So iteration will end , when we have 1 element left i.e. for any
i, which will be our last iteration:

1=n/2^{i};

2^{i}=n;

after taking log

i= log(n);

so it concludes that the number of iterations requires to do
binary search is log(n) so** the complexity of the binary search is log(n)**

It makes sense as in our example, we have n as 8 . It took 3
iterations(8->4->2->1) and 3 is log(8).**So If we are dividing input size by k in each iteration,then
its complexity will be O(logk(n)) that is log(n) base k.**

Lets take an example:**:**

int m=0; // executed log(n) times for (int i = 0; i < n; i=i*2) { m=m+1; }

**Exercise:**

Let's do some exercises and find the complexity of the given code:

**1,**

int m=0; for (int i = 0; i < n; i++) { m=m+1; }

**2.**

int m=0; for (int i = 0; i < n; i++) { m=m+1; } for (int i = 0; i < n; i++) { for(int j = 0; j < n; j++) m=m+1; } }

**Ans:**

int m=0; // Executed n times for (int i = 0; i < n; i++) { m=m+1; } // outer loop executed n times for (int i = 0; i < n; i++) { // inner loop executed n times for(int j = 0; j < n; j++) m=m+1; }

Complexity will be :n+n*n —>O(n^2)

**3.**

int m=0; // outer loop executed n times for (int i = 0; i < n; i++) { // middle loop executed n/2 times for(int j = n/2; j < n; j++) for(int k=0;k*k < n; k++ ) m=m+1; } } }\:

int m=0; // outer loop executed n times for (int i = 0; i < n; i++) { // middle loop executed n/2 times for(int j = n/2; j < n; j++) // inner loop executed log(n) times for(int k=0;k*k < n; k++ ) m=m+1; } } }

Complexity will be n*n/2*log(n)–> n^2log(n)

** 4.**

int m=0; for (int i = n/2; i < n; i++) { for(int j = n/2; j < n; j++) for(int k=0;k < n; k++ ) m=m+1; }

**Ans:**

int m=0; // outer loop executed n/2 times for (int i = n/2; i < n; i++) { // middle loop executed n/2 times for(int j = n/2; j < n; j++) // inner loop executed n times for(int k=0;k < n; k++ ) m=m+1; }

Complexity will be n/2*n/2*n –> n^3