COMPSCI 61B Lecture Notes - Lecture 17: Stopwatch, Big O Notation, Symbolic Execution
1 Jun 2017
School
Department
Course
Professor
Document Summary
Basic suite of autograder tests on the following operations: load t print t select * from t1, t2. If you haven"t nished join, do so asap. An engineer will do for a dime what any fool will do for a dollar. Objective: find a pair of duplicates in a sorted array. Given sorted array a, nd indices i and j where a[i] = a[j] Silly algorithm: create a list of all pairs and iterate through pairs. Better algorithm: for each number a[i], just look at a[i+1], and return true the rst time you see a match. Technique 1: measure execution time in seconds using a client program. Unix has a built in time command that measures execution time. Bad: varies with machine, compiler, input data, etc. Technique 2: count operations for some xed input size. Bad: still input dependent, doesn"t tell you actual time. Give statement counts or runtime in terms of input size.
