2.8: A few examples of asymptotic notation

Last updated
Save as PDF

Page ID: 49269

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Generally, we use asymptotic notation as a convenient way to examine what can happen in a function in the worst case or in the best case. For example, if you want to write a function that searches through an array of numbers and returns the smallest one:

function find-min(array a[1..n])
  let j :=  $\infty$ 
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  return j
end

Regardless of how big or small the array is, every time we run find-min, we have to initialize the i and j integer variables and return j at the end. Therefore, we can just think of those parts of the function as constant and ignore them.

So, how can we use asymptotic notation to discuss the find-min function? If we search through an array with 87 elements, then the for loop iterates 87 times, even if the very first element we hit turns out to be the minimum. Likewise, for \(n\) elements, the for loop iterates \(n\) times. Therefore we say the function runs in time \(O(n)\).

What about this function:

function find-min-plus-max(array a[1..n])
  // First, find the smallest element in the array
  let j :=  $\infty$ ;
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  let minim := j
  
  // Now, find the biggest element, add it to the smallest and
  j :=  $-\infty$ ;
  for i := 1 to n:
    j := max(j, a[i])
  repeat
  let maxim := j
  
  // return the sum of the two
  return minim + maxim;
end

What's the running time for find-min-plus-max? There are two for loops, that each iterate \(n\) times, so the running time is clearly \(O(2n)\). Because \(2\) is a constant, we throw it away and write the running time as \(O(n)\). Why can you do this? If you recall the definition of Big-O notation, the function whose bound you're testing can be multiplied by some constant. If \(f(x)=2x\), we can see that if \(g(x)=x\), then the Big-O condition holds. Thus \(O(2n)=O(n)\). This rule is general for the various asymptotic notations.