CMPT 125 Lecture 7: L7 P2
21 Dec 2018
School
Department
Course
Professor
Document Summary
Negative example: f(n) = n3 g(n) = n. Take n > c, then f(n)/g(n) = n3/n = n2 > c. this does not satisfy the equation. --> log2(n/2) = log2(n) - log2(2) = log2(n) f5(n) = (log(n))10 f7(n) = n log(n) + 100n f1(n) = n2 + 100n. O(n2) f4(n) = 2n3 + 100n + 108 f3(n) = n3 log(n) + 400n2 f2(n) = 2n + n6 + 100n f6(n) = 99n + log(n) + 4n. Goal: search for a given element in an array. If we do not know how the elements are arranged in the array, we can use a linear search (for loop), and go over all elements in the array one after another. In the worst case, the element we are looking for may be the last element in the array, or may not be in the array. (length of array when searching for an element in an unsorted array. )
