Common functions in algorithms

The Constant Function

$f(n) = c$

Note that any other constant function, $f(n) = c$, can be written as a constant c times g(n). That is, $f(n) = cg(n)$ in this case.

The Logarithmic Function

f(n) = logb n, for some constant b > 1.

The function is defined as follows:

$x = log_bn$ if and only if $b^x = n$

The Big-Oh" Notation

We say that $f(n)$ is $O(g(n))$ if there is a real contant $c > 0$ and an integer constant $n_0 >= 1$ such that:

$$f(n) <= cg(n), \quad for \quad n >= n_0$$

Recursion

Factorial



In [8]:

    
def fact(n):
    if n ==  0:
        return 1
    else:
        return n * fact(n-1)
    
print(fact(3))

BinarySearch



In [20]:

    
def BinarySearch(myList, val, low, high):
    mid = (low + high)//2   #this tripped me up. Can we low + (high-low)//2?
    
    if low > high:
        return False
    if myList[mid] == val:
        return True
    elif val < myList[mid]:
        return BinarySearch(myList, val, low, mid-1)
    else:
        return BinarySearch(myList, val, mid+1, high)

myList = [1,2,3, 10, 20, 35]
BinarySearch(myList, 35, 0, len(myList)-1)









    Out[20]:





True

Recursively reversing a Sequence (or a subset of it)



In [44]:

    
def reverse(S, start, stop):
    if start < stop - 1:
        S[start],S[stop-1] = S[stop-1],S[start] 
        reverse(S, start+1, stop-1)
        
s = [1,2,3,4,5]
reverse(s,0,len(s))
print(s)









    



[5, 4, 3, 2, 1]

How about iteratively?



In [52]:

    
import math
def ireverse(S, start, stop):
    swaps = math.ceil((stop - start)/2)
    
    for x in range(swaps):
        swap(s, start+x, stop-x)

def swap(s, index1, index2):
    temp = s[index1]
    s[index1] = s[index2]
    s[index2] = temp

s=[1,2,3,4,5,6]
ireverse(s,0,len(s)-1)
print(s)
ireverse(s,2,5)
print(s)









    



[6, 5, 4, 3, 2, 1]
[6, 5, 1, 2, 3, 4]



In [ ]: