Computer Science 2210A/B Lecture Notes - Lecture 1: Lexicographical Order, Big O Notation, Data Structure

• School: Western University
• Department: Computer Science
• Course: Computer Science 2210A/B
• Professor: Roberto Solis- Oba

Document Summary

In this and next lectures we introduce the con-cepts of: Given a set s of elements and a particular ele-ment x the search problem is to decide whether x s. This problem has a large number of applications: The solution of a problem has 2 parts: how to organize data. Data structure: a systematic way of organizing and accessing data: how to solve the problem. Algorithm: a step-by-step procedure for performing some task in finite time. For simplicity, let us assume that s is a set of n integers stored in non-decreasing order in an array l. This way of solving the search problem is called linear search. 1, if x 6 l i 0 while (i < n) and (l[i] 6= x) do i i + 1 if i = n then return 1 else return i. Linear search is no the only way of solving the search problem, there are many other solutions.