Furthermore, an analysis will show that performing N inserts on an initially empty binomial queue will take O(N) worst-case time. Indeed, it is possible to do this operation using only N − 1 comparisons; we leave this as an exercise.
I read this in one data structure book.I understood insertion takes constant time on average and on worst case it takes O(log n).I can't understand what that statement is saying.
During an insert operation, every comparison is followed by the merging of two trees (the node to insert is a tree of order 0). The merge operation reduces the total number of trees by 1, and no operation will split trees or increase their number.
So, starting with N individual nodes, i.e., N trees of order 0, if we do N-1 comparisons, then we will do N-1 merges and will be left with only 1 tree. No further merging would be possible at that point, so at most N-1 comparisons are necessary.