Specify the running time of each of the following algorithms. You must fully explain your answer for each of the question!
a) O(n)
Explanation : We can see that for loop will run
from 1 to n so it will run n+1 times. One time extra because when i
will be n+1 so condition will fail. Statements inside for loop will
run for n time. So time complexity of algorithm is O(n)
b) O(min(n,m))
Explanation : We can see that for loop will run
from 1 to min ( n, m) so it will run min(n,m)+1 times. One time
extra because when i will be n+1 or m+1 so condition will fail.
Statements inside for loop will run for min(n,m) time. So time
complexity of algorithm is O(min(n,m))
c) O(mnpq)
Explanation : 4 nested loop, One inside the other
. Each loop will run for its range time and a,ong iwth its range
because of outer loop. Hence the time complexity is O(mnpq)
d) O(n4)
Explanation : 4 nested loop, One inside the other
. Outer loop will run for n time, the first inner loop will run for
n time itself and n times because of outer loop so its
n2 . Similarly 2nd inner loop will run for n3
time, and the inner most loop will run for n4
time. Hence the time complexity is O(n4 )
(e)O(nm)
Explanation While loop will run for n time, and
inner loop loop will run for m time itself and n time because of
outer loop so its nm time. hence the time complexity is
O(nm)
Thanks, let me know if there is any concern. PLEASE RATE if you
think its helpful
Specify the running time of each of the following algorithms. You must fully explain your answer...
Analyze the running time of the following algorithms asymptotically. (a) Algorithm for-loop(n): P = 1 for i = 1 to 5n^2 do p = p times i return p (b) Algorithm for-loop(n): s = 0 for i = 1 to n do for j = I to n do s = s + i return s (c) Algorithm WhileLoop(n): x = 0; j = 2; while (j = n){x = x+ 1; j =j times 2;}
Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. Simplify your answers, expressing them in a form such as O(nk) or (nklog n) whenever possible. If the algorithm takes exponential time, then just give an exponential lower bound using the 2 notation. function...
Determine whether each of the following algorithms is fully correct, and prove that your answer is correct. Determine whether each of the following algorithms is fully correct, and prove that your answer is correct. 4 5 (a) [10 points) A(2) IN :TER,r> 1 1 r'= 2 p=0 3 while r'> 1 do p=p+1 r' = 2/2 6 return p OUT: p = log2 (b) [10 points) B(2) IN : r ER, 1 > 1 1 while r > 1 do...
For each of the following problems write a recurrence relation describing the running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using substitution and carefully computing lower and upper bounds for the sums. Simplify and express your answer as Θ(n k ) or Θ(n k (log n)) wherever possible. If the algorithm takes exponential time, then just give exponential lower bounds. 5. func5 (A,n) /*...
Write a recurrence relation describing the worst-case running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. 上午1:46 3月21日周四 令52%. " 5. endfor 6. return (r); function func4(A, n) *Aarray of n integers */ 1. if n s 20 then return (A[n]); 4. while (i < n/2) do 7. endwhile 8. x...
In this lab we are going to complete a profile of two sorting algorithms by running some tests to collect empirical data. 1. First we need to be able to generate some random integers. You can do this by including the following library : #include Now first run the following to generate a seed : srand (time(NULL)) You can then generate a random number using the function rand() 2. We will use two sort algorithms - Selection Sort and Bubble...
1. Analyze the running time of the following algorithm and write it using ( notation. You must show detailed calculation/derivation of your running time along with table to get marks. int sum = 0; for (int i=n; i)=1; i=i/2) { for (int j=1; j<=i; j*=2) { sum+=i*j; } }
Consider recursive divide-and-conquer algorithms with the following descriptions. For each, determine the running time in Big-Theta notation. If necessary, you may assume that the regularity condition holds. You do not need to prove your result. You may use the Master Theorem (n3) work per Performs 8 recursive calls on problems half the size of the input and performs recursive call. Consider recursive divide-and-conquer algorithms with the following descriptions. For each, determine the running time in Big-Theta notation. If necessary, you...
Below is a linear time complexity algorithm Max-Min-VER1 to find the biggest and smallest element a given list. Input: A is a given list Output: two integers Example: Given A = {1, 5, 9, -3}. It returns -3 (the smallest element), and 9 (the biggest element) Max-Min-VER1(A, n) Line 1: large ← A[0] Line 2: for I from 1 to n - 1 do Line 3: large ← Math.max(large, A[I]) Line 4: small ← A[0] Line 5: for I from...
Algorithm performance Give the order of magnitude Theta () for the following algorithm. Explain why your answer is correct. GET VALUES for A_1, A_2, .. ., A_n, and B_1, B_2, .. ., B_n Get value of n i = 1/* set i equal to 1 */DO WHILE (i lessthanorequalto n)/* for each of the n values in A */j = 1/* set j equal to 1 */DO WHILE (j lessthanorequalto n)/* Do n times *1 IF Ai = Bj THEN...