COMP 250 Study Guide - Midterm Guide: Linked List, Merge Algorithm, Abstract Data Type

67 views7 pages

Document Summary

For each algorithm below, indicate the running time 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. Running time in big-oh notation i i 2 x x + 1. Algorithm example(n) x 0 for i 1 to n do. Algorithm exam1(n) i 1 while (i < n) do. Algorithm exam2(n) x 0 for i 1 to n do x x + 1. Algorithm exam3(n) for i 1 to 1000 while j < i do. Algorithm exam4(n) i n while (i > 0) do i i 10 for j 1 to n i do j 1 j j + 1 + log(i) + j. Hint: don"t spend more than a constant amount of time on this one! The following algorithm takes a linked list as input and check if it has a certain property.