I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(n) comparisons. Basically it needs to compare the ith element with i+1th element, then i+1 to i+2 element and so on.
The adversary needs to make sure that algorithm does most of the work; so I am thinking about dynamically creating input array, and making the algorithm to compare all the elements.
In this video, he is also using adversary argument to prove equality testing (finding duplicates) and in it he is using majority voting technique.
I am however, still quite confused how do we implement such a strategy to prove lower bounds. What sort of adversary we need to design?
Any help will be appreciated. Thanks