Can anyone give an example of an algorithm that works for O(log) n or O(n*log n) , and explain where this relationship is established?
I need to write an algorithm to find out if there are two identical elements in the array, working for O(n*log n) .

    1 answer 1

    O (log n) - search in a binary search tree, binary search. O (n log n) - quick sort.

    • @a_gura why search in binary search tree-O (log n)? - dropitlikeitshot
    • 3
      Because at each node of the tree we will look half of the rest. Put in the tree 16 nodes. At the first stage, take half of the tree - 8 nodes, then 4, then 2, then the element will be found. Total 4 steps to search, 2 ^ 4 = 16, log (2) 16 = 4 - iksuy
    • 2
      If the tree is not balanced, then the search may be O(n) . Naive quick sort implementations can be O(n**2) . - jfs