Order

Order of algorithms

Introduction

The order notation gives us some idea of how efficient an algorithm is. We can do an average case, best case and worst case scenarios. We write the function as it computes the steps or operations in terms of n the input size. We can also think of the function as it computes the time or space but we will do it in terms of operations or steps to make it easier to understand the concept of Order.

We use the below 2 rules to help us.

1) If f(n) is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted.

2) If f(n) is a product of several factors, any constants (terms in the product that do not depend on n can be omitted.

Linear Search

Consider the algorithm linear search. The worst case is a loop that runs n times if n is the size of the array. The variable n is the input in this case. We have a comparison step inside the for loop.

for( int i1=0 ; i1 < length ; i1++ )

{

if ( arr1[i1] == element )

return ( i1 ) ;

}

Let's say that the statements

if ( arr1[i1] == element )

return ( i1 ) ;

If we consider the comparison statement as a single step. We can then write our equation to compute n input size as:

= 1 step* n

Using the second rule we take out the step part and state that the order is O(n) . What about the case when we have an input that has no match. Well we still have n comparison steps .

This tells us that say for input size n of 10 we are going to have 10 steps and if we increase the size to 20 then we will have 20 steps.

Best case

We will find the element in the first position so we have O(1) .

Average case .

We can assume that each element in the array is likely to be found with the same probability. For say 5 elements with values

1 2 3 4 5 0 1 2 3 4 We can find 1 with 1 operation. So the total number of operations is 1+2+3 .. 5 = 15 and average case is 15/5 = 3 For n elements We have the sum as n*( n+1 ) / 2 = sum divided by n gives us ( n +1 ) /2 = n/2 + 1/2 We can discard 1/2 using rule 1) and discard the 1/2 in 1/2 * n to get an Order(n)

Let's say we have 2 nested for loops.

for( int i1=0 ; i1<n ; i1++ )

for( int i2=0 ; i2<n ; i2++ )

{

//Some statement A

}

The variable i1 starts from 0 to n then we have the statement executed n times. Since i1 in the outer loop is going to run n times For each of those runs the inner runs "i2" is going to n times so we will have the inner statement executed ( n * n ) times.

= step 1 * n * n = n power 2 steps

Writing it as order gives us O( n power 2 ) .

If n is 10 and the time taken is 100 seconds . The steps that the algorithm took was 100. That means it took 100 seconds to execute 100 steps. One step takes 1 second to execute.

Then if we increase n to say 20 then the number of steps is 400 and so it will take 400 seconds to execute an input of size 20 . This tells us that O( n power 2 ) is very inefficient when compared to O(n ) .

Exercise

1) In the above example O( n power 2) if we increase n to 40 then what is the time taken to execute . Assume 1 step takes 1 sec.

2) The below expressions are for the number of steps . Find out the order using the rules 1 and 2 for simplifying the order.

a) n + 5

b) n*n + 3n + 4

c) 5*n*n + 300*n + 40000

d) (n2 + n) · (n + 1)

Binary Search

Let un analyze the binary search algorithm .

We can look for an element that does not exist in the array and that will give the max number of steps.

while ( left <= right )

{

int mid = ( left + right ) / 2 ;

if ( arr1[mid] == element )

return mid ;

else if ( arr1[mid] < element )

left = mid + 1 ;

else

right = mid - 1 ;

} //while

If n is 8 and our value is -1 and assume that does not exist and all the rest of the values are bigger than -1 then our steps are as:

left = 0 right = 7 mid = 3

left=0 right =2 mid = 1

left = 0 right = 0 mid = 0

left = 0 right = -1 come out of the loop

We have 2 power 3 + 1 step at the end.

We can write 3 as log 8 or log n where our base is 2. . So our equation is now

log n steps + 1 step

Using rule 1 we can take out the 1 step .

O ( log n )

This tells us that the algorithm is very efficient.

Average Case for Binary Search

Let's assume we have 7-8 elements . We can choose 7 or 8 based on our convenience.

On the first iteration we compare 1 element.

1 iteration 1 element 2 iterations applies to 2 elements 3 iterations applies to 4 elements Total iterations = 1 + 4 + 12 = 17/7 = 2.4 The 1 2 3 is up to log n . The actual calculations is bit complicated but the order is O(log n ) .

https://sceweb.uhcl.edu/yang/teaching/csci3333spring2011/Average%20case%20analysis%20of%20binary%20search.pdf

Bubble Sort Analysis

public static void bubbleSort2( int arr1[] )

{

boolean exchangeHappened = false ;

for ( int limit=arr1.length-1 ; limit > 0 ; limit-- )

{

boolean exchangeHappened = false ;

for ( int i1=0 ; i1< limit ; i1++ )

{

//Some steps

}

}

if ( exchangeHappened == false )

return ;

}

for input of size n = 4 we get

limit = 3 2 1

Inner loop runs = 3 2 1

We use the formula :

1+ 2 +3 ...k = ( k * (k+1 )) / 2

1+2 +3 = ( n * (n+1)) /2 + 2 steps

Our n = n-1

(( n-1) * n ) / 2

( n2 - n ) / 2

1/2 n2 - 1/2n

O (n power 2 )

Selection Sort

public static void selectionSort( int arr1[] )

{

for ( int i1=0 ; i1<arr1.length -1 ; i1++ )

{

int min = arr1[i1] ;

int minIndex = i1 ;

for ( int j1=i1+1 ; j1< arr1.length; j1++ )

{

if (arr1[j1] < min )

{

min = arr1[j1] ;

minIndex = j1 ;

}

} //for

arr1[ minIndex ] = arr1[i1] ;

arr1[ i1 ] = min ;

} //for

}

if length is n = 4

Outer loop runs i1 = 0 , 1, 2

Inner loop runs 1 2 3 2 3 1

3 2 1

We use the same logic for bubble sort 2 to conclude that the order is O( n power 2 ) .

Normally a single for loop of size n will produce O(n) and 2 nested for loops will produce O( n power 2 ) .

Exercise

1) What is the order of the below function ?

void function1( int n1 ) { for( int i1=0 ; i1 < 10; i1++ ) { for( int j1=0 ; j1 < n1; j1++ ) { cout << "j1:" << j1 << endl ; } } }

2) What is the order of the below function ?

void function1( int n1 ) { for( int i1=0 ; i1 < n1; i1++ ) { for( int j1=0 ; j1 < n1; j1++ ) { for( int k1=0 ; k1 < n1; k1++ ) { cout << "j1:" << j1 << endl ; } } } }

3) What is the order of the below function ?

void function1( int n1 ) { for( int i1=0 ; i1 < n1/10; i1++ ) { for( int j1=0 ; j1 < n1/10; j1++ ) { cout << "j1:" << j1 << endl ; } } }

4) What is the order of the below function ?

void function1( int n1 ) { for( int i1=0 ; i1 < n1; i1++ ) { cout << "i1:" << i1 << endl ; } for( int i1=0 ; i1 < n1; i1++ ) { cout << "i1:" << i1 << endl ; } }

5)

Let's say we have 5 elements( integers ) in an array . Show an array with 5 values

that will lead to to the worst case for insertion sort. Calculate the Order for insertion

sort.

Tower of Hanoi

void towerOfHanoi( int n1, char from_rod, char aux_rod, char dest_rod ) { if ( n1 == 1 ) { cout << "Move disk 1 from rod " << from_rod << " to rod " << dest_rod << endl ; return ; } towerOfHanoi(n1-1, from_rod, dest_rod, aux_rod); cout << "Move disk " << n1 << " from rod " << from_rod << " to rod " << dest_rod << endl ; towerOfHanoi(n1-1, aux_rod, from_rod, dest_rod ) ; }

For the case of 1 ring we have 1 step . The if condition would be executed. 1 -> 1 For 2 rings we have: tower( 1 ) 1 statement tower ( 1) We know that tower( 1 ) is 1 step so for 2 rings we have:2 -> 1 + 2*1 For 3 rings we have 3 -> 1 + 2( 1+ 2*1 ) = 1 + 2 + 2*2 = 3 + 2*2 4 -> 1 + 2( 3 + 2*2* ) = 1 + 6 + 2*2*2 We can see that the power of 2 grows with each number of rings and can guess that the order is O( 2 power n ) . The above is not a mathematical proof but we can get some idea about the result.

https://www.geeksforgeeks.org/time-complexity-analysis-tower-hanoi-recursion/

Merge Sort

Let's say we have 8 elements

8 7 6 5 4 3 2 1 n = 8 Merge ( 8) = 1 step to find the middle + mergesort ( 4 ) + mergesort ( 4 ) + merge The last part merge works with 8 elements . Regardless of how large the 2 blocks are we are going to work with 8 elements so the number of steps will be 8 . Similarly Merge( 4 ) 1 step to find the middle + mergsort( 2 ) + mergsort ( 2 ) + + merge 4 steps Merge( 2 ) will be 1 step to find the middle mergesort( 1 ) + mergesort( 1) + merge 2 steps Let's draw this in a hierarchy : n Time n steps 4 4 n steps 2 2 2 2 n steps 1 1 1 1 1 1 1 1 n steps The number of levels is log n + 1 and each level we have n steps. Equation is ( log n + 1 ) * n = n logn + n Using rule 1 we can discard n and are left with O( n log n )

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort

Quick Sort

This is not a rigorous mathematical analysis but something to give us an idea We assume the worst case is when the partitions are not equal at all . So for 4 elements .

2 3 4 1

The pivot is 1 and we have n-1 comparisons plus 1 swap so for n we have n steps . For the remaining partition of ( n-1 ) we have ( n-1 ) steps when we reach a partition of 2 then we have 2 steps. For partitions of size 1 and 0 we have 0 steps .

c(n) + c ( n-1 ) + c( n-2 ) + .... + 2 = c * ( n+1 ) ( n/2 ) - 1

We actually get O( n power 2 ) in the worst case for quick sort. However the best and the average order is O( n log n ) .

Heap Sort

// Build heap (rearrange array) for (int i1 = n / 2 - 1; i1 >= 0; i1--) heapify(arr, n, i1 ); We are going through n/2 elements . The levels are log n in our complete tree. The call heapify will be executed log n times. So the first time to build the heap will be (n/2) * log ( n ) Next we have a for loop that runs n-1 times and each time heapify is called so our steps are: ( n -1 ) * log n = n log n - log n Complete expressions is ( n/2) log n + n log n - log n Using 1 we discard log n n log n ( 1/2 + 1 ) Using Rule 2 we discard ( 1/2 + 1 ) and are left with O( n log n )

Exercise

1)

What is the order of the following functions?

int function1 ( int n ) { if ( n <= 0 ) return 1 ; cout << n1 << endl ; function1 ( n1 -1 ) ;} 2)

What is the order of the following program ?

int function1 ( int n ) { if ( n <= 1 ) return 1 ; cout << n1 << endl ; function1 ( n1 / 2 ) ;}

int main(){ int n ; cin >> n ; for ( i1=0 ; i1 < n ; i1++ ) function1( n ) ; }

Fibonacci Numbers

1)

Reference

https://www.baeldung.com/cs/fibonacci-computational-complexity

//The Fibonacci series is : //0 1 1 2 3 5 8 //0th 1st 2 3 4 5 6 public static int fibonacciNumberRecursive( int nth ) { if ( nth == 0 ) return 0 ; if ( nth == 1 ) return 1 ; //TO DO Write code that will return the fibonacci value

of nth number return ( fibonacciNumberRecursive(nth-1) +

fibonacciNumberRecursive(nth-2) ) ; }

Time for

T(n) = T( n-1 ) + T( n-2 ) + 1 Assume T(n-1) is approx T(n-2) T(n) = 2* T(n-1) + 1 T(n-1) = 2*T( n-2) + 1 Substituting T(n) = 2* ( 2*T(n-2 ) + 1 ) + 1 = 2*2* T(n-2) + 3 T( n-2 ) = 2*T(n-3 ) + 1 T(n) = 2*2*2*T(n-3) + 7 T(n-3) = 2*T(n-4) + 1 T(n) = 2*2*2*2*T(n-4) + 15

When n is 4 then we have 2 power 4 + 15 . T( 0 ) is just order of 1 because for n=0 and n=1 we have a single step. The order seems to growing exponentially . The order is O( 2 power n ) .

Exercise

Find the order for the iterative Fibonacci sequence

//The Fibonacci series is : //0 1 1 2 3 5 8 //0th 1st 2 3 4 5 6 public static int fibonacciNumberIterative( int nth ) { if ( nth == 0 ) return 0 ; if ( nth == 1 ) return 1 ; int fib1 = 0 ; int fib2 = 1 ; for( int i1=2 ; i1 <= nth ; i1++) { int temp = fib1 + fib2 ; fib1 = fib2 ; fib2 = temp ; } return ( fib2 ) ; }