Learning Algorithms

Chapter 2. Analyzing Algorithms

In this chapter, you will learn:

• How to use the Big O notation to classify the performance of algorithms (in time or storage)

• Several performance classes, including:

  • O(1) or constant

  • O(log N) or logarithmic

  • O(N) or linear

  • O(N log N)¹

  • O(N²) or quadratic

• How asymptotic analysis estimates in terms of N the time (or storage space) required by an algorithm to process a problem instance of size N.

• How to work with arrays whose values appear in ascending, sorted order.

• The Binary Array Search algorithm to locate values in a sorted array.

This chapter introduces the terminology and notation used by theoreticians and practitioners alike in modeling the performance of algorithms in terms of computational performance and resource usage. When evaluating the runtime performance of your software program, you might be perfectly satisfied, in which case you can continue to use the application as is. But if you want to improve runtime performance, this book shows you where to start—with the program’s data structures and algorithms. You are faced with some specific questions:

Am I solving a specific problem in the most efficient way?

There may be other algorithms that would significantly improve performance.

Am I implementing an algorithm in the most efficient way?

There can be hidden performance costs that can be eliminated.

Should I just buy a faster computer?

The exact same program will have different runtime performance based ...