Define an algorithm whose running time is O(tetration(2,n)), the power tower of n 2s. Or worse, describe a problem which requires that amount of time. Are there interesting such problems?
Perhaps we do not think of such things because of the hopelessness of ever computing them.
Intimidating at a lesser scale is O(n!), growing faster than any exponential function (but less than 2-EXPTIME). What problems require factorial time?
No comments :
Post a Comment