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

Popular posts from this blog

ubuntu - PHP script to find files of certain extensions in a directory, returns populated array when run in browser, but empty array when run from terminal -

php - How can i create a user dashboard -

javascript - How to detect toggling of the fullscreen-toolbar in jQuery Mobile? -