# Average-case space complexity

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. )

• If you could be more specific, I think you will be more likely to get answers to your question. By "average-case space complexity" of a problem, do you mean the average of the minimum space required to solve each of set of instances of some problem? I'm not sure that's well defined, although it is not something I have thought about in great detail. If you mean something simpler, like the average space complexity of a particular algorithm when solving a problem, then I think your question might not get many answers because there are just so many possibilities. (continues in next comment) Mar 24, 2011 at 5:26
• (continued from above) In particular, if that's what you mean, your question might be a bit too general for TCS SE: cstheory.stackexchange.com/faq Maybe, maybe not. The first example that pops into my head is ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , but many randomized data structures have space analyses. Mar 24, 2011 at 5:29
• @jbapple: I cannot follow your criticism. I thought that it was clear from the question that the asker is looking for works on the space-complexity counterpart of Levin’s average-case time complexity, and still think so even after reading your comments. I cannot answer the question not because the question is unclear, but because I do not know the subject well and I do not know any such work. Mar 27, 2011 at 22:34
• @Tsuyoshi Ito: You're right. Mar 28, 2011 at 3:53
• interpreting "average case analysis" as "the algorithm is allowed to err a few times" makes it sound like randomized analysis. Mar 29, 2011 at 6:45