• Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint
Share this Page URL
Help

Chapter 10. Optimizing JavaScript for Ex... > Algorithms and Data Structures

Algorithms and Data Structures

As we learn in computer science classes, global optimizations (such as algorithm and data structure choices) determine in large part the overall performance of our programs. For larger values of “n,” or the number of input elements, the complexity of running time can dominate any local optimization concerns. This complexity is expressed in O-notation, where complexity or “order” is expressed as a function of n. Table 10.1 shows some examples.

Table 10.1. Run-Time Complexity of Classic Algorithms[12],[13]
Notation Name Example
O(1) constant array index, simple statements
O(logn) logarithmic binary search
O(n) linear string comparison, sequential search
O(nlogn) nlogn quicksort and heapsort
O(n2) quadratic simple selection and insertion sorting methods (two loops)
O(n3) cubic matrix multiplication of n×n matrices
O(2n) exponential set partitioning (traveling salesman)


[12] Kernighan and Pike, The Practice of Programming, 41.

[13] Andrew Hunt and David Thomas, The Pragmatic Programmer: From Journeyman to Master (Boston, MA: Addison-Wesley, 1999), 179.


PREVIEW

                                                                          

Not a subscriber?

Start A Free Trial


  
  • Creative Edge
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint