Publishers of technology books, eBooks, and videos for creative people

Home > Articles > Web Design & Development > PHP/MySQL/Scripting

  • Print
  • + Share This
This chapter is from the book

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 Algorithms12, 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 nxn matrices

O(2n)

exponential

set partitioning (traveling salesman)


Array access or simple statements are constant-time operations, or O(1). Well-crafted quicksorts run in nlogn time or O(nlogn). Two nested for loops take on the order of nxn or O(n2) time. For low values of n, choose simple data structures and algorithms. As your data grows, use lower-order algorithms and data structures that will scale for larger inputs.

Use built-in functions whenever possible (like the Math object), because these are generally faster than custom replacements. For critical inner loops, measure your changes because performance can vary among different browsers.

  • + Share This
  • 🔖 Save To Your Account