Computer Science:Data Structures:Asymptotic Notation - eMyTextBooks

Computer Science:Data Structures:Asymptotic Notation

Asymptotic Notation

In order to analyze which data structure or algorithm is the best suited for the job, it is necessary to understand how a data structure or algorithm behaves over time and space. An important tool in this analysis is asymptotic notation.

Big Oh Notation 

For non-negative functions, f(n) and g(n), if there exists an integer n₀ and a constant c > 0 such that for all integers n > n₀, f(n) ≤ cg(n), then f(n) is Big Oh of g(n). This is denoted as "f(n) = O(g(n))".

If graphed, g(n) serves as an upper bound to the curve you are analyzing, f(n). It describes the worst that can happen for a given data size.

Big Omega Notation 

For non-negative functions, f(n) and g(n), if there exists an integer n₀ and a constant c > 0 such that for all integers n > n₀, f(n) ≥ cg(n), then f(n) is omega of g(n). This is denoted as "f(n) = Ω(g(n))".

This is almost the same definition as Big Oh, except that "f(n) ≥ cg(n)", this makes g(n) a lower bound function, instead of an upper bound function. It describes the best that can happen for a given data size.

Theta Notation 

For non-negative functions, f(n) and g(n), f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is denoted as "f(n) = Θ(g(n))".

This is basically saying that the function, f(n) is bounded both from the top and bottom by the same function, g(n).

Little Oh Notation 

For non-negative functions, f(n) and g(n), f(n) is little oh of g(n) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) = o(g(n))".

This represents a loose bounding version of Big Oh. g(n) bounds from the top, but it does not bound the bottom.

Little Omega Notation 

For non-negative functions, f(n) and g(n), f(n) is little omega of g(n) if and only if f(n) = Ω(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) = ω(g(n))".

Much like Little Oh, this is the equivalent for Big Omega. g(n) is a loose lower boundary of the function f(n); it bounds from the bottom, but not from the top.

How asymptotic notation relates to analyzing complexity

If you think of the amount of time and space your algorithm uses as a function of your data over time or space (time and space are usually analyzed separately), you can analyze how the time and space is handled when you introduce more data to your program.

This is important in data structures because you want a structure that behaves efficiently as you increase the amount of data it handles. Keep in mind though that algorithms that are efficient with large amounts data are not always simple and efficient for small amounts of data. So if you know you are working with only a small amount of data and you have concerns for speed and code space, a trade off can be made for a function that does not behave well for large amounts of data.

A few examples of asymptotic notation

Generally, we use asymptotic notation as an 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 := 
  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 that part of the function as a constant and ignore it.

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 := ;
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  let min := j
  
  // Now, find the biggest element, add it to the smallest and
  // return the sum of the two
  j := ;
  for i := 1 to n:
    j := max(j, a[i])
  repeat
  let max := j
  
  return min + max;
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.

Edit this chapter (http://en.wikibooks.org/w/index.php?title=Computer_Science:Data_Structures:Asymptotic_Notation_content&action=edit)