I don\'t need help with the sorting part for both questions, i just need someone
ID: 3847628 • Letter: I
Question
I don't need help with the sorting part for both questions, i just need someone to explain to me how to do the time complexity for each in Big Oh notation. I don't need a code, I just need someone to show me the process by hand
Explain how the following list would be sorted and give the time complexity for each in Big Oh notation:
[ 25, 4, 7, -1, 9, 11, 3]
Using SELECTION SORT:
Your Answer:
[-1, 4, 7, 25, 9, 11, 3]
[-1, 3, 7, 25, 9, 11, 4]
[-1, 3, 4, 25, 9, 11, 7]
[-1, 3, 4, 7, 9, 11, 25]
Time complexity for SELECTION SORT.
________________
Using MERGE SORT
Your Answer:
[25, 4, 7, -1, 9, 11, 3]
[4, 25, -1, 7, 3, 9, 11]
[-1, 3, 4, 7, 9, 11, 25]
Time complexity of MERGE SORT.
____________________
Explain how the following list would be sorted and give the time complexity for each in Big Oh notation:
[ 25, 4, 7, -1, 9, 11, 3]
Using SELECTION SORT:
Your Answer:
[-1, 4, 7, 25, 9, 11, 3]
[-1, 3, 7, 25, 9, 11, 4]
[-1, 3, 4, 25, 9, 11, 7]
[-1, 3, 4, 7, 9, 11, 25]
Explanation / Answer
Selection-Sort(A)
1 For j = 1 to (A.length - 1)
2 i = j
3 small = i
4 While i < A.length
5 if A[i] < A[small]
6 small = i
7 i = i + 1
8 swap A[small], A[j]
The basic operation for this algorithm is the comparison in the inner loop. Both loops are executed n times, i.e. the basic operation is executed n*n times n^2. The time complexity for selection sort is O(n^2). It is same for worst best and average cases
[ 25, 4, 7, -1, 9, 11, 3]
Answer
[-1, 4, 7, 25, 9, 11, 3]
[-1, 3, 7, 25, 9, 11, 4]
[-1, 3, 4, 25, 9, 11, 7]
[-1, 3, 4, 7, 9, 11, 25]
Merge Sort
mergesort( int [] a, int left, int right)
{
if (right > left)
{
middle = left + (right - left)/2;
mergesort(a, left, middle);
mergesort(a, middle+1, right);
merge(a, left, middle, right);
}
}
Assumption: N is a power of two.
For N = 1: time is a constant (denoted by 1)
Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus time to merge two arrays each N/2 elements.
Time to merge two arrays each N/2 elements is linear, i.e. N
Thus we have:
(1) T(1) = 1
(2) T(N) = 2T(N/2) + N
Next we will solve this recurrence relation. First we divide (2) by N:
(3) T(N) / N = T(N/2) / (N/2) + 1
N is a power of two, so we can write
(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1
(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1
(6) T(N/8) / (N/8) = T(N/16) / (N/16) +1
(7) T(2) / 2 = T(1) / 1 + 1
Now we add equations (3) through (7) : the sum of their left-hand sides will be equal to the sum of their right-hand sides:
T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 =
T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN
(LogN is the sum of 1s in the right-hand sides)
After crossing the equal term, we get
(9) T(N)/N = T(1)/1 + LogN
T(1) is 1, hence we obtain
(10) T(N) = N + NlogN = O(NlogN)
Merge sort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be log2nlog2n and for each level we perform O(n)O(n) work hence total time taken will be O(nlogn).