c - TimeComplexity of the the following merging k linked lists -

http://www.geeksforgeeks.org/merge-k-sorted-linked-lists/

with reference link: how divide , conquer strategy gives o(nk log k) complexity please explain. also,i have coded same in little bit different way. difference being in pattern of merging. merge first 2 linked result , result other linked list.

what complexity of this?

node * mergek(){     int n;     puts("enter number of linked list want enter");     scanf("%d",&n);     node ** arr=malloc(sizeof(node *)*n);     int i=0;     for(i=0;i<n;i++){         arr[i] = takeinput();     }     for(i=0;i<n;i++){         print(arr[i]);     }     node * temp=null;     for(i=0;i<n;i++){         if(i==0){             temp=merge(arr[i],arr[i+1]);             i=i+1;         }            else{             temp=merge(arr[i],temp);         }        }     return temp;     } 

i wanted know if have same complexity or no e. o(nklog(k)) complexity.

the number of merges remain same.

while number of merges remain same, pattern of merging makes time complexity lot worse. assuming have merge() function merge 2 sorted linked lists in o(n + m) time (where n = size of first list, m = size of second) , o(1) space, consider following analysis in assume each list has on average n elements.

• first merge o(n + n), we're merging 2 n-sized lists
• second merge o(2n + n), we're merging 1 n-sized list our 2n-sized list
• third merge o(3n + n)...and on.

at point have add of additions inside big-oh get:

o(2n + 3n + 4n + 5n + ... + kn) 

the sum of these n terms n*(k(k+1))/2 because (k(k+1))/2 sum of first k numbers. taking constant factors , lower order terms out of (k(k+1))/2, can see o((k(k+1))/2) = o(k^2), giving algorithm o(n*k^2) time complexity.

i wrote small article on problem , analyzed further, extent of complexity differences. should check out here

---

to answer other question on how divide , conquer approach yield o(nk*log(k)), think of how merge sort works.

if have $n$ items, merge sort n amount of work, many times takes pairwise merge n items before become 1 whole list. number log(n) (log base 2 of n), takes number of steps proportional nlog(n) (again, realize we're doing n amount of work because there n elements @ play, log(n) times). reason merge sort has break list down individual elements before merging them because single unit smallest thing can definition, sorted, without doing work sort it.

in our case, each list sorted, can treat each of k lists (of size ~n) element sorted definition. there no need break sorted list down further. since there k lists each n elements, there n*k elements @ play. luckily since each list sorted though, have merge k "elements" instead of n*k list elements. same logic prevails, in have merge k elements/lists together. since each list takes o(n) time merge, opposed o(1) when dealing n*k individual elements, takes time proportional o(nk*log(k)).