COM SCI 32 Lecture Notes - Lecture 10: Tinder, Popping, Binary Logarithm

• School: UCLA
• Department: Computer Science
• Course: COM SCI 32
• Professor: N A C H E N B E R G

Document Summary

We can measure an algorithm based on how many computer instructions it takes to solve a problem of a given size as a function n of the size of the input data. When we measure this way, we get two bene(cid:210)ts: we can compare two algorithms for a given sized input, we can predict the performance of those algorithms when they are applied to less or more data. This is the idea between the big-o concept used in computer science. The big-o approach measures an algorithm by the gross number of steps that it requires to process an input of size n in the worst case scenario. Algorithm x requries 5n^2 + 3n + 20 steps to process n items. With big-o, we ignore the coe(cid:213)cients and lower-order terms of the expression, so the big-o of algorithm x is n^2.