1) Review the following algorithms (assume any undeclared variables are declared earlier ) int int count rand ( ) F for (int 0: 1 < N; i+ +) : 0 .3 rand ( ) ; a < 1.0 int num = rand ( ) ; : <1.5 += rand () if ( num < 0 .5 ) 2 . 0 += rand () count + = 1 ; 1. 5 rand ( ) ; rand ( ) : i ii int count = 0 : int count = 0, for (int i 1 = 0; 1 < N: i+ + int i = N; if (unlucky) if Iunlucky while (i > 0) count = count + : count i / = 2: iii . iv. int count = 0: for line i = 0: i . - 1; it+) for (int i = 0; i < for (int j = 0; j < M-i-1; j+ +1 int num = rand ( ) ; if (atjl > a [j+1]) if[ num < 0 .5 Swap (a [j ], ali + 1]) ; count += 1; 7 int num = count: for (int ] =0: 1 < num: j+ +) count = count + ]: vi. For each of the above answer each of the following a) What is the number of operations of the best , worst and average cases ? b) Describe the best , worst and average case using Big -0 notation. c) Describe each algorithm's s overall performance using the tightest possible class in Big -O notation d) Describe each algorithm's overall performance using the tightest possible class in Big - Q notation. e ) Describe each algorithm's overall performance using Big -@ notation Selecting from one or more of the above which is the best way to succinctly describe the performance of each algorithm using asymptotic notation 2 . Arguably , the most commonly used asymptotic notation used is frequently Big -O. Discuss why this is so commonly the case Is it true that e7 Phalgorithm always takes longer to run than an enlog nalgorithm? Explain your answer. 4. Answer whether the following statements are right or wrong and explain your answers nlog n GOD ORna n D n9 0 10'n 60 8An n log n 609 hank

1.)

• IN the best case scenario, the value of unlucky is False, so that the program does not enter the loop at all.
• The operations that takes place in this scenario are:
• 1.) int count = 0; repetition = 1
• 2.) int i = N; repetitions = 1
• 3.) if(unlucky); repetition = 1
• Total number of operation = 3

2.)

• In worst case scenario, unlucky must be True, and the program has to enter the loop
• the loop will be repeated until i becomes 0
• note that i halves at every iteration. So, the total numbers of iteration = log N
• The operations that takes place in this scenario are:
• 1.) int count = 0; repetition = 1
• 2.) int i = N; repetition = 1
• 3.) if(unlucky); repetition = 1
• 4.) while(i>0) repetition =  log N + 1
• 5.) count += i; repetition = log N
• 6.) i /= 2; repetition = log N
• total number of operation = 1 + 1 + 1 + log N + 1 + log N + log N = 3log N + 4

Step-by-step explanation

3.)

• In average case scenario, the program has to enter the while loop. As it enters the while loop, it has to complete the iteration as in worst case scenario because there is no condition to let the program break out of loop in between.
• So, the number of operations in average case will be the same as that of worst case
• total number of operation = 3log N + 4

b.)

1.) Best case:

• In the best case scenario , the number of operations = 3.
• So, the best case time complexity is O(1)

2.) worst case:

• In the worst case scenario, the number of operations = 3logN + 4
• so, the worst case time complexity is O(log N)

3.) average case:

• In the average case scenario, the number of operations = 3logN + 4
• so, the average case time complexity is O(logN)

c.)

• The Big-O notation just deals with the upper bound of the runtime complexity. In this case it is O(log N)
• So, basically, the runtime of the algorithm doubles as N gets squared.

d.)

• The Big - Omega notation only deals with the lower bound of the algorithm. In this case it is Ω (1) [ omega(1) ]
• It means that, the runtime of the algorithm is unchanged irrespective of the value of N.
• Of course, the big-omega notation only takes the best case scenario into consideration

e.)

• The Big-Theta notation deals with both upper and lower bounds of the algorithm
• The best case time complexity can be given as Θ (1) [Theta (1) ]
• The worst case time complexity can be given as Θ (log N) [Theta (log N)]
• The runtime of the algorithm is always between these bounds

f.)

• The big-Theta might be the best way to describe an algorithm.
• While big-O notation deals with the upper bounds and the big-Omega notation deals with the lower bound, the big-Theta notation takes both upper bounds and lower bounds into consideration. Since, both of these bounds are required to describe an algorithm, the big-Theta notation might be the best fit to describe an algorithm