Q1. Find the total number of operations of the following pseudo code. Show your calculation for every line of the code (similar to the first example of Slide 20 of Lecture 1). Finally write the total number of operations by O notation. [2 marks]

for (i=0; i<=n; i++)

for (j=0; j<=n; j++)

x = x+y;

for (i=0; i<=10*n; i++)

x = x+y;

Q2. Take your 7-digit Taibah University student ID as the input array. Draw the steps of the all partitions of quick sort for this input array until the array is completely sorted. Take the first element of the array as pivot. Draw the array after every step of the partition. Show pivot, S1, S2 and Unknown at every step.

Q3. Draw the complete recursion tree for merge sort analysis for n=2⁵ (similar to Slide 23 of Lecture 2). Draw the complete tree up to the last level. Then calculate the number of steps for merging at each level in the right side. Finally, find the total number of steps for merging by numbers (not in O notation). Everything should be done for n = 2⁵ (not for n = 2^m).