Introduction
•	Reading: Dale, 2.1, plus pp. 159-164
•	Software efficiency
•	Definitions
•	Big O notation
•	Abstract Data Types
Software efficiency
•	What do you think it means for a program to be efficient?
•	How would you determine if a program is efficient?
Metrics of software efficiency
•	Metric: measurement (ex: height, age, speed)
•	For software, the most common metrics are:
•	(Execution) time: time it takes to run program
•	Space: maximum memory used by program
What are Data Structures? Why do they exist?
•	"Data": the information used
•	"Structures": organizing the information
•	How data is stored
•	Implemented operations (methods)
•	Organization can have a great impact on performance
•	Storage media may limit practical options
What are Algorithms? Why do they exist?
•	Step-by-step process for solving a problem
•	Must be clearly defined
•	General solution: why is this important?
•	Data structure used restricts feasible algorithms
•	Ex: Explain why binary search is not used on linked lists
What "general" means
•	Works for different sets of data
•	Not only different values, but different types
•	Ex: Sorting algorithm should work for integers, reals, strings, records
•	Works for different programming languages
•	Define steps in pseudocode
Comparing algorithms
•	One possible approach:
•	Implement each algorithm in a program
•	Compare the performance of the programs
•	What might go wrong?
Scalability
•	For small amounts of data, efficiency is less important
•	Algorithm efficiency becomes important for large amounts of data
•	Really big databases may contain petabytes of info (10^15 bytes)
•	Scalability: how well does algorithm perform as amount of data increases
Order of growth
•	To focus on scalability, concern is with the order of increase in the efficiency metric as amount of data increases
•	Ex: Computing sum of list of numbers
•	Sum of 50 numbers should take about 10 times as long as adding 5 numbers
•	Getting value of first number of any list should take about the same time
Big O notation
•	An algorithm's complexity is measured based on the size of the data
•	Let n = number of data elements
•	An algorithm is O(1) if the execution time is constant, regardless of data size ()
•	ex: getting value of first number in a list of numbers
•	ex: checking if one of the first 2 characters in a string is a 'z'
Big O notation
•	O(n) means linear: ex: execution time for summing list of numbers
•	O(...) is a metric for the worst-case: 
•	ex: linear search only requires checking one element in the best case, but worst case requires looking through all n elements
Big O notation, cont'd
•	In general, an algorithm is O(f(n))
•	as data size increases, execution time/space/etc. increases proportional to f(n)
•	How does execution time change if we are checking if a value is in the first half of a list
•	We do not retain coefficients or lesser order factors
•	Ex: Displaying "Done" after computing the sum takes time, but the same amount of time even if the list has a gazillion numbers
Other examples
•	As length of list increases from 8 to 128, how many more values do we need to check for binary search?
•	O(log n) (base of log does not affect overall order)
•	Bubblesort is O(n^2)
•	Better sorting algorithms are O(nlog n)
•	Many algorithms for finding optimal solutions are O(2^n)
Speed, revisited
•	For pure speed, assembly language is fastest
•	Why do people use other programming languages?
•	Ex: writeability, maintainability
•	Often simple, straightforward solutions help produce more reliable software sooner
Abstract Data Type
•	An algorithm can be implemented in many different ways
•	To understand an algorithm, focus on what is true for any implementation
Abstract Data Type
•	For data, focus on essential data elements and methods
•	Abstract Data Type (ADT): "A data type whose properties are specified independently of any particular implementation" (Dale, p. 66)
Abstract Data Type and the Software Process
•	Application (or user) level : what is the data for a specific problem
•	Logical (or abstract) level : design-level  (ADT)
•	Implementation level : data structure
•	Next: the list ADT