# Find the largest number in a list or array of numbers.

```
numbers = [5,6,2,7,6,2,0,4]
max = numbers[0]
for number in numbers:
if number > max:
max = number
```

**The Big-0 of this program is n O(n)**

# Search for a number in an array or list

Try to search and see if the number 0 is in the list or array

```
numbers = [5,6,2,7,6,2,0,4]
for number in numbers:
if number == 0:
return True
```

**The Big-0 of this program is n O(n)**

# Search for a number in a Sorted array or list

Try to search to see if the number 80 is in the list or array.

the needle is the number we are searching for.

- Note
- We call this algorithm the binary search.

```
# binary search
haystack = [0,11,25,38,41,54,66,79,80,94]
needle = 80
lo = 0
hi = len( haystack )
while lo < hi:
mid = int( (lo + hi) / 2 )
if needle > haystack[ mid ]:
lo = mid + 1
elif needle < haystack[ mid ]:
hi = mid
else:
print "found %d which is the %d index of the list" % ( haystack[ mid ], mid )
break
```

- Worst case in 8 item list is 3 compares.
- Worst case in 16 item list is 4 compares.
- Worst case in 32 item list is 5 compares.

**The Big-0 of this program is n O(logn) - base 2**

This is a very good algorithm!

# Bubble Sort an array or list

This is a bubble sort algo using python, don't use this in production this is for learning only!

**BIGO( n^2 )**

```
def bubsort( mylist ):
while True:
swapped = False
for i in range( 0, len( mylist ) - 1 ):
if mylist[i] > mylist[i+1]:
temp = mylist[i]
mylist[i] = mylist[i+1]
mylist[i+1] = temp
swapped = True
if not swapped:
break
```

# python recursion

```
def gcd( x, y ):
"""Find greatest common divisor of two numbers recursion"""
if y == 0:
return x
else:
return gcd( y, x%y )
def gcd2( x, y ):
"""find the greatest common divisor of two numebrs"""
for i in range( 2, x ):
if x % i == 0 and y % i == 0:
return i;
if __name__ == "__main__":
print gcd( 287, 91 )
print gcd2( 287, 91 )
```

: )

# python heap

A heap is a binary tree where the parent is always larger than its children.

Determine the last nodes that are leaves: (total number of items / 2) - 1

```
def build_heap( data ):
"""Turn any array or list (data) into a heap tree"""
j = ( len( data ) / 2 ) - 1
i = j
while i >= 0:
current = data[i]
#insert_heap( current, i , length of subtree i - 1 )
i -= 1
```

Most operating systems use heap tree to manage memory.

# hash table

Don't use this in production! python has a datatype called dict, use that instead!!!

This is an example of building a hash table.

- sparse table or direct address table.

Assume that:

- Totle number of keys <= the size or the array.
- no 2 elements have the same keys.

Algorythm:

- Create A[0, max -1]
- put key x into A[x]

Example:keys = 5,2,3,7 A = list() A[2] = 2 A[5] = 5 A[3] = 3 A[7] = 7

- Hash table

Assume that:

- keys = {0,1,2,3,4,n-1}
- total numebr of keys > the size of the array

Algorythm:

- A = list(0, max -1)
- put key x into A[ hash(x) ]
hash function like md5 or sha256 hash(x) = x mod 6

If you have collisions there could be a problem.

A few 'easy' hash functions:

example = 11141874

- Truncation, choose part of the data to use for storage.
A[874] = 11141874

- Folding, split up data and add them up:
first 2 chars + last 2 chars

A[85] = 11141874

Modular

k mod m where m is the array size

example m = 10

# Extras

- Note:
- Count the total number of comparisons in terms of n.

for( int i = 2 ; i<= n ; i++ ){ } Worst case there will be at least two comparisons. Or at least n - 1 comparisons.

# Big-O notation compared to Complexity

Always look for the worst case when finding the Big-O

- O( 1 )

- Constant complexity

- O( log n )

- Logarithmic complexity

- O( n )

- Linear complexity

- O( n log n )

- n log n complexity

- O( n^b )

- Polynomial complexity

- O( b^n ), where b>1

- Exponential complexity

- O( n! )

- Factorial complexity

## Comments

## Leave a comment