Author: Unknown
Subject: adversary
Date: Sunday, 01 Mar 2020, 00:59:59

what is the point of an adversary argument? is it essentially listing out all possible combinations, minimizing the number of combinations deleted each round (ie. making the algorithm take as many steps as possible), and then calculating the number of steps required?

why does an adversary argument imply that an algorithm is optimal?

i also don't get the point of the three examples in lecture 9. under the element uniqueness problem, there is equality testing, inequality testing and anything goes. for inequality testing, we are told to sort the items first. but then the procedure compares each possible pair. so what is the algorithm and what is the procedure? i'm very confused about what the actual algorithm is, what the adversary is, and how the adversary proves that the algorithm is optimal. 

for anything goes, there was no complexity analysis or adversary provided. what is the point of anything goes? also, what does anything goes mean?