How many comparisons does the insertion sort use to sort the list n, (n - 1), (n
ID: 3810007 • Letter: H
Question
How many comparisons does the insertion sort use to sort the list n, (n - 1), (n - 2), ..., 2, 1? Determine whether each of these functions is 0(x^2) a) f(x) = 10 b) f(x) = x^2 + 100 c) f(x) = x log x d) f(x) = x^2/2 e) f(x) = 2^x For each of the five functions above, determine if they are Ohm(x^2) and whether if they are Theta(x^2). Give Phi-notation for the number of arithmetic operations performed by the following code. Explain how you got your answer: t: = 1 for i: = 1 to n for j = 1 to i t: = t + 1Explanation / Answer
3.
b f(x)=x^2 +100
c.f(x)=(x^2/)2
in asymptotic analysis we ignore constants since for greater values of x these constants will have negliigible values as compared to x^2 term and thus won't influence the ultimate result.
hence we can write
b. f(x)=x^2
c.f(x)=x^2
both are theta(x^2) becuase no matter what they are going to grow with rate of x^2.
4.
t=1 theta(1) i.e it constant it is executed only once.
for i=1 to n theta(n+1) it is executed n + 1 times 1 for checking if i>n
for j=1 to i theta(n) all the things in side a loop are executed the number of times that loop executes
t=t+1 theta(n*i) all the things in side a loop are executed the number of times that loop executes times outer loop.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.