suppose a computer executes one instruction in a microsecond and an algorithm is known to have a complexity of O(2^n), if a maximum of 12 hours of computer time is given to this algorithm, determine the largest possible value of n for which the algorithm can be used
+4
A:
No can do.
O(2^n) means that there exists C such that limit n->infinity f(n)<=C*(2^n).
But this C can also be the number of 023945290378569237845692378456923847569283475635463463456 so even 12 hours cannot ensure that it will run even on small input.
Itay
2010-09-20 14:44:56
So the smallest possible value is clearly 0. :)
Vatine
2010-09-20 14:50:28
@Vatine not necessarily, since only the limit is guaranteed even that might take 14 hours.
cobbal
2010-09-20 14:53:55
+2
A:
Insufficient information. An algorithm that is O(2^n) doesn't necessarily take exactly 2^n steps for input of size n, it could take a constant factor of that. In fact, it could take C*(2^n)+B operations, where C and B are constant (that is, they don't depend on n), they are are both integers, and C >= 1 and B >= 0.
ktho
2010-09-20 14:51:25
+1
A:
Well, as O(2^n) is an exponential complexity and you're asked for the "largest possible exponent", you're trying to find an N, so that 2^N is less than or equal to 12 hours (* 3600 seconds, * 1000000 for the microseconds). From there, you can either use logarithms to find the right value or estimate an initial N and iterate until you find a value.
Vatine
2010-09-20 14:51:26