given a degree sequence for n vertices i.e.$d_1,d_2,….d_v$.what is worst time complexity to determine if a simple graph is possible with the given degree sequence?
answer given as:$O(n^2logn)$.
according to me,for first we have to sort them which will take O(nlogn) and then we have to decrease the degrees which will take O(n) additionally ,so for first pass it will take O(nlogn) +O(n)=O(nlogn).now we have degrees which are almost sorted for which insertion sort will take O(n) to sort and additionally O(n) for decrease the degrees ,so total O(2n)=O(n).so total time = for first pass {O(nlogn)}+for n-1 pass O(n) =O($n^2$.
correct me if i m wrong.thank you
