Estimate the complexity of inserting strings into the DMU of a list?

Question

Algorithms

There is a doubly linked list with dynamic arrays of pointers to strings. When a file is loaded, the lines are distributed in an orderly manner into nodes. Each next node is 2 times larger than the previous one. The size of the first node is 10 lines. When simultaneously loading a file from 1 to 1000 times, 175 lines long and 11kb in weight, the growth order of the function is y=7725x^2.001. Question. Is this normal and is it possible to achieve an order of growth of a function less than a quadratic one?

Answer 1

You need to put the lines in a self-balancing tree (AVL, red-black, etc.). In C++, it is implemented in set and muliset STL containers. The complexity of adding will be - logarithm