0

When i see that problem i think i could use divide and conquer to solve algorithm chart

second her's my code program code sorry i can't write it here cause i wrote it in inline compiler and the file didn't saved

the code work well but when i calculate the n comparison it was bigger than n + log(n) -2

my question(problem) is i can't solve the problem based on specific run time or specific comparison i solve the problem then calculate the comparison

i speak in general not just for that problem

how can i design(think about) an algorithm based on run time, is there steps to follow or what

Karim Ata
  • 343
  • 6
  • 15
  • Go through this link : https://stackoverflow.com/questions/9889679/find-second-largest-number-in-array-at-most-nlog%e2%82%82n%e2%88%922-comparisons – DRV Feb 15 '20 at 10:16

1 Answers1

1

Run an elimination tournament (n - 1 comparisons). The second largest must be among those who lost to the champion, and there are log n of them. Find the largest of the candidates in log(n) - 1 comparisons.

The hardest part is to design an efficient data structure to have the lists of the defeated opponents handy. This is highly non-trivial. For example, take a look at Alex Stepanov's solution.

PS: I highly recommend the entire course.

user58697
  • 7,808
  • 1
  • 14
  • 28