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).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.