24 Sep
2007
24 Sep
'07
4:27 p.m.
Matthew Brecknell wrote:
Andrew Coppin:
Anybody happen to know what the time complexity of "transpose" is?
Bas van Dijk:
The worst case time complexity is O(r*c) where 'r' are the number of rows and 'c' are the number of columns.
I believe Bas is correct, though it might be worth elaborating on what he means by "worst case".
Because transpose is quite lazy, it need not necessarily result in a quadratic time complexity on every use.
On the other hand, my program needs the entire transposed list, so... ;-)