Page 1 of 1
What is the time complexity of the following algorithm? Assume that the number of elements in array A is equal to N. A:
Posted: Fri May 20, 2022 1:43 pm
by answerhappygod
- What Is The Time Complexity Of The Following Algorithm Assume That The Number Of Elements In Array A Is Equal To N A 1 (95.12 KiB) Viewed 29 times
What is the time complexity of the following algorithm? Assume that the number of elements in array A is equal to N. A: array of numbers low: lowest index of array (0) mid: index of array A, low <mid < high high: highest index of array A (Number of elements -1) 1 2 3 4 5 6 7 8 9 10 11 12 13 function F(A, low,mid, high) for 0 <= i <=mid B
=A for 0 < i < (high-mid) C=A[i+mid+1] i=0; j=0; k=0 while( i <mid AND j<(high-mid)) if(B<C[j]) A[k]=B i=i+1 else A[k]=C[j] j=j+1 k=k+1 if (i>mid) for j <= m < high-mid A[k]=C[m] k=k+1 if(j >= (high-mid)) for i <= m <mid+1 A[k]=B[m] k=k+1 end function 14 15 16 17 18 19 20 21 22 23 Theta(NlogN) none of the others Theta(N) Theta(logN) Theta(2*N)