COMP 250 Study Guide - Midterm Guide: The Algorithm, Recto And Verso, N100

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Michael Langer

Document Summary

Use the verso of a page if you need more space to answer. Unless noted otherwise, all logarithms are in base 2. Indicate the running of each of the algorithms below using the simplest and most accurate big-oh notation as a function of n. assume that all arithmetic operations can be done in constant time. You don"t need to show your steps or prove anything. Running time in big-oh notation x x + 1. Algorithm example(n) x 0 for i 1 to n do. Algorithm exam1(n) i 1 while i < n do i i + 100. Algorithm exam2(n) x 0 for i 1 to n do for j 1 to i do x x + 1. Algorithm exam3(n) i 1 k 1 while i < n do i i + k k k + 1. Algorithm exam4(n) k 1 for i 1 to 1000 for j 1 to i k (k + i j) (2 + i + j)