Polynomial Or Exponential Running Time Solution – Intro to Theoretical Computer Science

Polynomial Or Exponential Running Time Solution – Intro to Theoretical Computer Science


So, here’s the correct answers. The first one, 2^nlog(n).That is clearly an exponential running time because 2^n is exponential. Now, what about the next one, 2^log(n). Well, 2^log(n) is actually O(n) because… So, having the logarithm and exponent, well, actually cancel out the exponents. So, that is O(n). So, although it might look exponential, if you don’t look closely enough, that is actually a polynomial running time. Now, O(1.00001^n), that is going to be a very, very slowly growing function, but nevertheless, it’s exponential. So, this is the correct answer, and n^1000, that’s basically the opposite. It’s a polynomial that will grow rapidly fast and you would never want an algorithm actually with that running time, but nevertheless, it is a polynomial running time. Now, this is algorithm–well, you already figured that out I guess because it’s 2^nn²,that is an exponential running time algorithm, that’s why it’s really bad. Now, as you see with those two examples here, there’s something to be said about saying that we consider polynomial running time to be acceptable and exponential running time to unacceptable, but in general, what you will find is that polynomial time algorithms tend to have a running time of n² or n³. So, there is not really any algorithm that I would know of, at least now that make sense that has a running time like this. So, it’s kind of okay from empirical experience to call a polynomial time algorithm, actually one with an acceptable running time, and the same thing is with exponential running time. So, when you have an exponential time algorithm, you will not have one that has in the base of figure like 1.00001^n. For some algorithms, you might have 1.1 or 1.2, but even then, it’s a fairly rapidly growing function. So, it’s also okay to call exponential running time algorithms unacceptable in general.

2 thoughts on “Polynomial Or Exponential Running Time Solution – Intro to Theoretical Computer Science”

Leave a Reply

Your email address will not be published. Required fields are marked *