Search code examples
insertbinary-search-treecode-complexity

finding the complexity of insertion to avl tree

If I have an empty avl tree and I want to insert a set of ordered numbers (1, 2, ... k), why the complexity is O(k).
thank you

Solution

  • It's more of a math question, so here is the deal

    AVL tree has a time complexity of log(n) for inserting an element with n nodes inside the tree

    so from your question, with a set of number (1,2,3,...,k) you wanted to insert, the time complexity would be like this

    summation from i=1 to i=k of log(i) (i.e. log1 + log2 + log3 + ... + logk)

    which is equals to

    log(k!)

    which is approximately equals to

    k*log(k) (By using Stirling's approximation)

    So to answer your question, it should be O(k log k) instead of O(k)