0

I am struggling to establish the 'O' complexity of finding the kth smallest element in an array using tournament algorithm.

I have formed the reverse-tree ,with the smallest element at the root node of the inverted tree.[(n-1)*log n]

Now we ascend the inverted tree starting from the smallest element at the bottom.
Wouldn't finding the index of the root element at each level be a O'n' operation again?

I would have to traverse the array at each level to find the index of the smallest(root) element via 'n' comparisons.[n*log n]
Is there any faster way to devise the index of the root element at each level?

OnABauer
  • 609
  • 4
  • 18
IUnknown
  • 9,301
  • 15
  • 50
  • 76

1 Answers1

1

You cannot simply go up the tree, for the leaf at the right of the parent of the smallest element is smaller than the grandparent of the smaller element. Like this: 9 / 7 / \ 5 8

I believe that the answer to your question is available at How to find the kth largest element in an unsorted array of length n in O(n)? (change largest to smallest and you will have a solution).

Community
  • 1
  • 1
rlinden
  • 2,053
  • 1
  • 12
  • 13