CMPSC 40 Lecture Notes - Lecture 14: Linear Search, Bubble Sort, Binary Search Algorithm
Document Summary
When we analyze the time the algorithm uses to solve the problem given input of a particular size, we are studying the time complexity of the algorithm. Measured in terms of the number of operations an algorithm uses. Use big-o and big-theta notation to estimate time complexity. Use time analysis to see whether it is practical to employ an algorithm to solve problems with input of a particular size. You can compare the efficiency of different algorithms for solving the same problem. Ignore implementation details (including the data structures used and the hardware/software platforms) When we analyze the computer memory the algorithm uses to solve the problem given input of a particular size, we are studying the space complexity of the algorithm. To analyze the time complexity of algorithms, determine the number of operations (i. e. comparisons, arithmetic operations) Estimate the time a computer may actually use to solve a problem using the amount of time required to do basic operations.