Review: The story so far...Searching an Unordered ListUnordered List Search AlgorithmSlide 4Slide 5Slide 6Cost of Unordered List Search AlgorithmOrder NotationSlide 9Order NotationExamples of Order NotationWhy Use Order NotationSo what order is our search algorithm?Review: The story so far...We want to determine what problems can be solved automatically.We made a formal model of our automatic computer.We stated two tests a problem must pass to be consideredcomputable: 1) solved by an automated process, 2) the process cannot take too long.We can tell if an automatedprocess exists if we can write an algorithm.How can we tell if an algorithm takes too long?Searching an Unordered List•This is the most basic search problem.•Problem Description–Given a list of elements in no particular order–Given a specific element called the KEY–Determine if the key is in the list.•Why search problems?–Logging on (username and password) –Telephone directory searches.–Web page retrieval involves searches.–Sending email and instant messages.Unordered List Search Algorithm•An algorithm takes input, operates on it, and produces output.•What are the inputs?–Unordered list and key.•What are the outputs?–A Boolean value (True or False)•What do we need to worry about?–Can it be done? (Is it computable?)–How efficiently can it be done?–What kind of data structures should we use?–What kind of search pattern should we use?Unordered List Search Algorithm•Inputs: Number list[n]; Number key•Other Data: Boolean answer; (Boolean means the only values allowed are "True" and "False")•Initialization: Assume list[n] and key are given to us.answer = False;•Computation: FOR i = 0 to (n-1) DOIF (list[i] equals key) THENanswer = True;quit algorithm;ELSEENDIFENDFOR•Outputs: return answer;Unordered List Search Algorithm•Is our algorithm any good?–It is correct, precise, incremental, and can be abstracted -- so yes.•Is it efficient?–We cannot answer until we have a method to determine its cost and compare against other algorithms solving the same problem.•The cost of an algorithm can be found simply by counting the number of operations that are performed. For our purposes an "operation" is a single assignment, comparison, or arithmetic operation.•The cost of our algorithm is shown on the next page in red.Unordered List Search Algorithm•Inputs: Number list[n]; Number key•Other Data: Boolean answer; (Boolean means the only values allowed are "True" and "False")•Initialization: Assume list[n] and key are given to us.answer = False;•Computation: FOR i = 0 to (n-1) DOIF (list[i] equals key) THENanswer = True;quit algorithm;ELSEENDIFENDFOR•Outputs: return answer;1111Cost of Unordered List Search Algorithm•We have identified 4 operations that add cost to the algorithm. •2 of them occur only once (the assignments of True and False to the variable "answer.")•2 of them may occur up to n times each, due to the loop.•The total cost is 2n + 2. This cost is exact.•We still aren't ready to compare yet. Computer science does not use exact costs, but uses approximate costs with a notation called order notation.Order Notation•We’ve said that Computer Science is concerned with computability–Is it computable?–How efficiently can we compute something?•The cost is measured in the number of operations required to complete the computation.–For searches and sorts we are concerned with comparison operations.•We typically talk about average costs and worst-case costs–Average costs tell you how much things usually cost.–Worst-case costs tell you how bad things can get.–The input data affects the cost of a specific computation.–A “bad” data set results in a worst-case cost.Order Notation•Most input data can have a size associated with it–Our searching algorithm had an unordered list with n elements–Similarly, we will sort lists with n elements in them soon–It is convenient to talk of problems of size n•We want to predict the computational cost of solving a problem of size n–Tells us if the problem is computable.–Tells us how long it takes to solve problems.–May tell us that only little problems (n is small) are solvable –Allows us to compare efficiency of algorithms.Order Notation•ORDER NOTATION allows us to relate computational cost to problem size.•For a problem of size n:–The solution may be of constant cost.–The solution may be of the order n, meaning cost = constant * n–The solution may be of the order n-squared, meaning cost = constant * n2–The solution may be exponential, meaning cost = nconstant.•The order notation for the above four cases is:–Constant equals O(k).–Order n equals O(n).–Order n2 equals O(n2). [In general order nk equals O(nk).]–Exponential equals O(kn).Examples of Order Notation•Examples:–Problem A has cost 1000*n [it is O(n)].–Problem B has cost 10 * n2 [it is O(n2)].Problem A, O(n) Problem B, O(n2)Size of Problem Cost CostN = 10 10,000 ops 1,000 opsN = 50 50, 000 ops 25,000 opsN = 100 100,000 ops 100,000 opsN = 500 500,000 ops 2,500,000 opsWhy Use Order Notation•The order (or cost) of a computation tells us whether it is computable or not:–All O(k) and O(n) problems are computable.–Most O(nk) problems are computable ( usually k = 1, 2, or 3)–Most O(kn) are only computable for very small n.•Order notation allows us to compare the efficiency of different algorithms that have been developed to solve the same problems.•Order notation allows us to compare the efficiency of our algorithms with known costs for problems.–You don’t want the cost of your algorithm to be larger than the known best costs for a problem.So what order is our search algorithm?•What is the worst-case cost?–Worst case is we have to look at and compare the entire list.–Worst case Cost = 2n + 2, so this is O(n).•Not only do algorithms have a cost, but problems do also. •It can be proven that our algorithm is as efficient as possible for the unordered search problem.–No algorithm could be less than O(n) for unordered search.–Algorithms can be slower (or require more operations than necesary) so O(n2) or worse would not be incorrect, just less