I am trying to find problems whose average-case space complexity has been analyzed.
More specifically, I am interested to know if there are any problems with a proven space complexity lower bound that is super-linear, and especially if there are any with an average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )
Thanks in advance