CMPSC 24 Lecture Notes - Lecture 10: Absolute Time And Space, Pseudocode
Document Summary
Units is the number of ticks based on computer"s clock (ticks/clocks_per_sec = seconds) Time to run the algorithm for a specific input/input size. Doesn"t tell us how the running time scales with the input size. Tied to the performance of the hardware (diff for diff computers) Have to wait for the program to finish running. A: b) iterative formula bc the number of function calls for the recursive formula is. Focus on the impact of the algorithm: Simplify the analysis of running time (ex: 3n^2 = n^2) Focus on trends as input size increases (asymptotic behavior) How does the running time of an algorithm increase with the size of the input in the limit (for large input sizes) Every computer can do some primitive operations in constant time (none of them depend on the size of the input) By inspecting the pseudo-code, we can count the number of primitive operations executed by an algorithm.
