**Data Structures**

Introduction - **Asymptotic Notation** - Arrays - List Structures & Iterators

Stacks & Queues - Trees - Min & Max Heaps - Graphs

Hash Tables - Sets - Tradeoffs

## Asymptotic NotationEdit

### IntroductionEdit

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 ===

#### DefinitionEdit

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(): 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 and a constant *c* > 0 such that for all integers , *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:

functionfind-min(arraya[1..n]) letj:= fori:= 1 ton:j:= min(j,a[i]) repeat returnjend

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 elements, the for loop iterates times. Therefore we say the function runs in time .

What about this function:

functionfind-min-plus-max(arraya[1..n])// First, find the smallest element in the arrayletj:= ; fori:= 1 ton:j:= min(j,a[i]) repeat letminim:=j// Now, find the biggest element, add it to the smallest andj := ; fori:= 1 ton:j:= max(j,a[i]) repeat letmaxim:=j// return the sum of the tworeturnminim+maxim; end

What's the running time for **find-min-plus-max**? There are two *for* loops, that each iterate times, so the running time is clearly . Because 2 is a constant, we throw it away and write the running time as . 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 . This rule is general for the various asymptotic notations.

**Data Structures**

Introduction - **Asymptotic Notation** - Arrays - List Structures & Iterators

Stacks & Queues - Trees - Min & Max Heaps - Graphs

Hash Tables - Sets - Tradeoffs