EECS 1019 Study Guide - Midterm Guide: The Algorithm

• School: York University
• Department: Electrical Engineering and Computer Science
• Course: EECS 1019
• Professor: Suprakash Datta

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).