Friday, February 20, 2009

Time Complexity, Intro to Searching

We walked through time complexity, space complexity and implementation complexity and explored common tradeoffs between these measures. We discussed the difference between saving space (using fewer pointers) and the concept of space complexity as a mathematical measure of space requirements for growing data sets. We discussed Big O notation and explored a number of examples for common time complexity solutions. We began to think about data structure and algorithm analysis - how to determine suitability for a particular scenario or requirement

We talked about Search and how its a critical problem in computer science, applicable to lists, graphs, trees and more. We talked about common search applications such as data record retrieval, mapping, web searching, and gaming. We explored the complexity tradeoffs between binary search and linear search and introduced the role that sorting plays when making decisions on a search algorithm. Finally, we walked through a couple of linear search algorithms and learned how the search-key and search-result are often different values.

• You can find the slides for today's lecture here.