Data Structures/Asymptotic Notation

< Data Structures

Asymptotic NotationEdit


There is no single data structure that offers optimal performance in every case. In order to choose the best structure for a particular task, we need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long two solutions will take to run, and choose the better of the two. We don't need to know how many minutes and seconds they will take, but we do need some way to compare algorithms against one another. Asymptotic complexity is a way of expressing the main component of the cost of an algorithm, using idealized (not comparable) units of computational work. Consider, for example, the algorithm for sorting a deck of cards, which proceeds by repeatedly searching through the deck for the lowest card. The asymptotic complexity of this algorithm is the square of the number of cards in the deck. This quadratic behavior is the main term in the complexity formula, it says, e.g., if you double the size of the deck, then the work is roughly quadrupled. The performance evalution of an algorithm is obtained by totalling the no of occurences of each operation when running the algorithm.

there are some asymptotic notations used as follows:

1:tightly bound(theta-notation),2:upper bound(o-notation),3:lower bound(omega-notation)

1:=== The O Notation ===


The O (pronounced big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete. for upper bound notation we can say that, f(n)=O(g(n)), if there are positive constants n0 and C such that to the right of n0,the value of f(n) always lies on or below Cg(n).

Practical ExamplesEdit

O(n): printing a list of n items to the screen, looking at each item once.

O(ln n): also "log n", taking a list of items, cutting it in half repeatedly until there's only one item left.

O(n^2): taking a list of n items, and comparing every item to every other item.

2:=== "Big-Omega Notation(lower bound)"=== For non-negative functions, f(n) and g(n), if there exists an integer n_{0} and a constant c > 0 such that for all integers n>n_{0}, 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.

3:==== 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).

The theta notation is denoted by Q.

A few examples of asymptotic notationEdit

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])
  return j

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])
  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])
  let maxim := j
  // return the sum of the two
  return minim + maxim;

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.