Name: Mennatullah Magdy Mahmoud Mostafa Elnashar
ID: 20201378920
Assignment 1(5 Marks)
1. (1Mark) Knowing the equation of θ ( g ( n ) ) (g(n)) = {f(n) : positive constants c1, c2,
1 2
and n0, such that n n0, 0 c1g(n) f(n) c2g(n)} , show that n −3 n=θ ( n )
2
2
1
c 1(n2 )≤( n 2−3 n)≤ c 2( n2)
2
By dividing the equation by n2
1 3
c 1≤( − )≤ c 2
2 n
1 3
c 1≤( − ) at n ≥ 7∧c 1<0.07
2 n
1 3
c 2≥( − ) at n ≥ 1∧c 2≥ 0.5
2 n
.
2. (1Mark) Show that 6n3 ≠ θ ( n2 )
By dividing the equation by n3
c 1 ( n2 ) ≤ 6 n3 ≤ c 2(n2)
By dividing the equation by n3
c1 c2
≤6≤
n n
Since c1 may equal c2, this violates the rule. So, 6n3 ≠ θ ( n2 )
3. (1Mark) Suppose we want to sort a reversed sorted array of length N=1million
elements. We choose the bubble sort. We choose computer A with speed = 106million
instructions per second. Calculate the time Computer A will take for sorting the
array? And what will be the time taken if we choose the merge sort? Take c = 50 for
both types of sorting
Bubble Sort:
Bubble sort has a worst-case time complexity of O(N^2), where N is the length of the array. For
an array of length N = 1 million, the number of comparisons required would be:
N * (N - 1) / 2 = 1,000,000 * (1,000,000 - 1) / 2 = 499,999,500,000
Since we are assuming a constant c = 50, the total time taken by Computer A to perform bubble
sort would be:
Time = c * number of comparisons / speed = 50 * 499,999,500,000 / (106 * 10^6) seconds
= 2,358,491 seconds (rounded to the nearest whole number)
Therefore, it would take Computer A approximately 2,358,491 seconds to sort the reversed
sorted array using bubble sort.
Merge Sort:
Merge sort has a worst-case time complexity of O(N*log(N)), where N is the length of the array.
For an array of length N = 1 million, the number of comparisons required would be:
N * log(N) = 1,000,000 * log(1,000,000) = 1,000,000 * 6 = 6,000,000
Since we are assuming a constant c = 50, the total time taken by Computer A to perform merge
sort would be:
Time = c * number of comparisons / speed = 50 * 6,000,000 / (106 * 10^6) seconds
= 3 seconds (rounded to the nearest whole number)
Therefore, it would take Computer A approximately 3 seconds to sort the reversed sorted array
using merge sort.
Therefore, we can see that merge sort is significantly faster than bubble sort for large arrays, and
it is a more efficient algorithm for sorting reversed sorted arrays.
4. (2Marks) Prove the correctness of Bubble Sort
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
First: Evaluation based on Termination property
The code satisfies the termination property because it contains two nested loops that run for a finite
number of iterations, and it also includes an optimization that terminates the algorithm early if the list is
already sorted. Therefore, the algorithm terminates in a finite amount of time for any input list.
Second: Evaluation based on Correctness property
The code satisfies the correctness property because it follows the standard bubble sort algorithm,
includes an optimization that checks for already sorted lists, does not modify the original input list, and
produces a new sorted list as output. Therefore, the algorithm produces the correct output for any valid
input.
Third: Evaluation based on Efficiency
The time complexity of the algorithm is O(n^2) in the average case due to the two nested loops that run
for n iterations each. The algorithm's space complexity is O(n) because it creates a new list of the same
size as the input list to store the sorted elements. Overall, the code for bubble sort is not considered the
most efficient sorting algorithm for large input sizes. However, it can be an appropriate choice for small
input sizes or for educational purposes due to its simplicity and ease of understanding.
