Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Is this correct for finding big o and calculating the cost and time for the counting-sort algorithm? If not, please explain why and what's wrong.


Is this correct for finding big o and calculating the cost and time for the counting-sort algorithm? If not, please explain why and what's wrong. When I add it up I get 4n + 4k -5 = o(n + k), but the book says is 2n + 2k

Counting-sort (A, B, k) Let C[0...K] be a new array for i = e to k c[i] = 0 for j=1 to A. length or n C[A[j]] = C[A[j]] + 1 for i=1 to k c[i] = C[i] + C[i-1] for j-n or A.length down to 1 B[C[A[j]] = A[j] C[A[j]] = C[A[j]] -1 Cost C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 Time 1 1 K K-1 n n-1 K K-1 n n-1 n-1

Step by Step Solution

3.41 Rating (148 Votes )

There are 3 Steps involved in it

Step: 1

I have accidently taken CountingsortA B k as the first line What you are ... blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Foundations of Financial Management

Authors: Stanley Block, Geoffrey Hirt, Bartley Danielsen, Doug Short, Michael Perretta

10th Canadian edition

1259261018, 1259261015, 978-1259024979

More Books

Students also viewed these Programming questions