Illustrative table for space/time complexity?

[ajvincent]

I've been thinking about drawing up a table for the repository main page to illustrate what the performance benefit would (or could) be here, in both time and space complexity.

Given m object graphs and n original objects:

Scenario	Complexity	m = 2 (typical)	Notes
Creating one revoker per proxy	Space: O(mn)	Space: O(n)	This is what we have now.
	Time: O(mn)	Time: O(n)
Creating one revoker per object graph pair	Space: O(mn)	Space: O(n)	Adding one slot on each proxy for the pointer to the mass revoker.
	Time: O(mn)	Time: O(n)
Revoking all proxies referring to one object graph	Time: O(mn)	Time: O(n)	This is what we have now.
			All proxies in that graph to other graphs, plus all proxies in other graphs pointing to objects in this graph.
Revoking an entire object graph via a shared revoker	Time: O(m)	Time: O(1)	Normal case (no proxy depends on a proxy in another graph)
	Time: O(2m-1)	Time: O(1)	Power set of graphs (when some proxy depends on another proxy, rare)
Revoking an entire membrane via proxy revokers	Time: O(mn)	Time: O(n)
Revoking an entire membrane via shared revokers	Time: O(m2)	Time: O(1)	Normal case (no proxy depends on a proxy in another graph)
	Time: O(2m)	Time: O(1)	Power set of graphs (when some proxy depends on another proxy, rare)

The exponential time complexities are scary at first, but really, not that bad. Because the number of object graphs, m is almost always tiny compared to the number of original objects, n.

[ajvincent]

I really need someone to check my math above.

In particular, I'm imagining revoking one object graph of entirely original objects, no proxies. That's going to be the worst-case scenario in a more-than-two object graphs situation.