the time efficiency of an algorithm by considering how many steps the algorithm requires as function of the input size searching is the process of finding particular item among collection linear search scans the collection from start to end and requires time linearly proportional to the size of the collection if the collection is sortedit can be searched using the binary search algorithm binary search only requires time proportional to the log of the collection size binary search is an example of divide and conquer approach to algorithm development divide and conquer often yields efficient solutions definition or function is recursive if it refers to itself to be well-foundeda recursive definition must meet two properties there must be one or more base cases that require no recursion all chains of recursion must eventually reach base case simple way to guarantee these conditions is for recursive calls to always be made on smaller versions of the problem the base cases are then simple versions that can be solved directly sequences can be considered recursive structures containing first item followed by sequence recursive functions can be written following this approach recursion is more general than iteration choosing between recursion and looping involves the considerations of efficiency and elegance sorting is the process of placing collection in order selection sort requires time proportional to the square of the size of the collection merge sort is divide and conquer algorithm that can sort collection in log time problems that are solvable in theory but not in practice are called intractable the solution to the famous towers of hanoi can be expressed as simple recursive algorithmbut the algorithm is intractable some problems are in principle unsolvable the halting problem is one example of an unsolvable problem you should consider becoming computer scientist exercises review questions true/false linear search requires number of steps proportional to the size of the list being searched