asymptotic complexity

suppose a computer executes one instruction in a microsecond and an algorithm is known to have 开发者_Python百科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

---

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.

---

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.

---

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.