Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter2 [2018/01/29 02:43] – [2.5 Priority Queues] nasona | courses:cs211:winter2018:journals:nasona:chapter2 [2018/01/29 16:20] (current) – [2.4 Common Runtimes] nasona | ||
|---|---|---|---|
| Line 191: | Line 191: | ||
| ==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? | ||
| + | * 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, | ||
| Line 275: | Line 277: | ||
| ==Questions== | ==Questions== | ||
| + | * Should the heap methods Delete(H, i) be used only in the context of ExtractMin(H) when a heap is implementing a priority queue because wouldn' | ||
| + | * I'm pretty sure the answer is yes, but I'm just double checking? Can a priority queue have multiple elements with the same priority? If so, how does the heap implemented queue decide which element to move to the root when the minimum is extracted when both of the children have the same priority? I'm pretty sure this would have to be dealt with in the part of Heapify-down that figures out the minimum of the two children of a deleted item. | ||
| ==Additional Information== | ==Additional Information== | ||
