C S 314 Chapter Notes - Chapter 2: Type Safety, Memory Address, Quicksort
13 Dec 2016
School
Department
Course
Professor
Document Summary
We will assume that basic operations take constant time. Later, we will consider some exceptions to this assumption: Some library functions may take more than o(1) time. We will want to be conscious of the big o of library functions. Memory access may be affected by paging and cache behavior. There may be hidden costs such as garbage collection. It is often easy to determine big o directly from code: Elementary ops such as +, =, a[i], v. f are o(1). The big o for a sequence of statements { ; ; } is the max of the big o of the statements. The big o for an if statement is the max of the big o of the test, then statement, and else statement. The big o for a loop is the loop count times the big o of the contents.
