EECS 1019 Study Guide - Midterm Guide: The Algorithm
![](https://s3.us-east-1.wasabisys.com/prealliance-avatars.oneclass.com/avatars/515914/small/RackMultipart20201118-71849-4b6192.png?1637711045)
![EECS 1019 Full Course Notes](https://new-docs-thumbs.oneclass.com/doc_thumbnails/list_view/2152519-class-notes-ca-york-eecs-1019-lecture2.jpg)
8
EECS 1019 Full Course Notes
Verified Note
8 documents
Document Summary
Solution: first let us prove the () part. Since 8n3 + c = 8, n0 = 1 in the de nition of (). Since 8n3 + c = 9, n0 = 1 in the de nition of o(). This completes the proof. n > 8n3 for n 1, we can use n 8n3 + n3 = 9n3 for n 1, we can use. Express your answer as a function of n. give using o() notation the worst-case running time. f1(n) 3 do for j n + 1 to 2n. 5 return v do v v + 1. Solution: line 4 runs exactly n2 times and adds 1 to v each time it executes. Therefore the nal value of v, which is returned, is n2. For the running time you can do a detailed analysis as done in the class or you can argue that because it has two nested loops, each running n iterations, so the running time is o(n2).