sorting - Counting sort running time -
the code fragment below link
int[] countingsort(int[] a, int k) { int c[] = new int[k]; (int = 0; < a.length; i++) //{1} c[a[i]]++; (int = 1; < k; i++) //{2} c[i] += c[i-1]; int b[] = new int[a.length]; (int = a.length-1; >= 0; i--) //{3} b[--c[a[i]]] = a[i]; return b; }
it states running time o(n+k) time .k range of input array .
can explain why running time o(n+k). ?
if @ code fragment , see {1} loop runs in n time , {2} runs in k time , third runs in n time total run time should o(2n+k) time . calculation incorrect? constant 2 ignored here ?
your calculation correct, because o(2n+k) = o(n+k)
.
for time complexity, polynomial degree important, not coefficients.
so; o(n) = o(2n) = o(3n) .... = o(xn)
please read https://en.wikipedia.org/wiki/time_complexity#linear_time
Comments
Post a Comment