Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:nasona:chapter2 [2018/01/29 16:18] – [2.4 Common Runtimes] nasona | courses:cs211:winter2018:journals:nasona:chapter2 [2018/01/29 16:20] (current) – [2.4 Common Runtimes] nasona | ||
|---|---|---|---|
| Line 192: | Line 192: | ||
| ==Questions== | ==Questions== | ||
| * When depicting exponential runtime do you want us to have a specific base like O(2^n) or would a general O(n^k) suffice? | * When depicting exponential runtime do you want us to have a specific base like O(2^n) or would a general O(n^k) suffice? | ||
| - | * | + | * Are there any instances in which O(n^2) arises without the presence of nested loops? |
| ==Additional Information== | ==Additional Information== | ||
| In class, we didn't really talk about O(2^n) or O(n!) in too much depth. It was really interesting and helpful to see that in the reading. Until doing the reading, I wasn't quite sure why O(2^n) was such a common or important runtime, but now it is obvious why. It is the natural runtime of a brute-force search algorithm, which we try to improve upon in all of the algorithms that we create in this class. Moreover, the way by which a factorial runtime comes about was more explicitly explained in the reading than in class. Although, we would hope to never have an algorithm that runs this efficiently, | In class, we didn't really talk about O(2^n) or O(n!) in too much depth. It was really interesting and helpful to see that in the reading. Until doing the reading, I wasn't quite sure why O(2^n) was such a common or important runtime, but now it is obvious why. It is the natural runtime of a brute-force search algorithm, which we try to improve upon in all of the algorithms that we create in this class. Moreover, the way by which a factorial runtime comes about was more explicitly explained in the reading than in class. Although, we would hope to never have an algorithm that runs this efficiently, | ||
