BigO, Complexity, Time Complexity, Space Complexity, Algorithm Analysis

In [1]:

    

def sumOfN(n):
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i
        
    return theSum
    
print(sumOfN(10))


    

    




55

In [2]:

    

def foo(tom):
    fred = 0 
    for bill in range(1,tom+1):
        barney = bill
        fred = fred + barney
    
    return fred

print(foo(10))


    

    




55

In [3]:

    

import time 

def sumOfN2(n):
    start = time.time()
    
    theSum = 0  # 1 assignment 
    for i in range(1,n+1):
        theSum = theSum + i # n assignments 
        
    end = time.time()
    
    return theSum, end-start  # (1 + n) assignements


    

In [10]:

    

for i in range(5):
    print("Sum is %d required %10.7f seconds " % sumOfN2(10000) )


    

    




Sum is 50005000 required  0.0015261 seconds 
Sum is 50005000 required  0.0011671 seconds 
Sum is 50005000 required  0.0009739 seconds 
Sum is 50005000 required  0.0009711 seconds 
Sum is 50005000 required  0.0009670 seconds 

In [11]:

    

for i in range(5):
    print("Sum is %d required %10.7f seconds " % sumOfN2(100000) )


    

    




Sum is 5000050000 required  0.0077779 seconds 
Sum is 5000050000 required  0.0062630 seconds 
Sum is 5000050000 required  0.0053980 seconds 
Sum is 5000050000 required  0.0049260 seconds 
Sum is 5000050000 required  0.0048888 seconds 

In [12]:

    

for i in range(5):
    print("Sum is %d required %10.7f seconds " % sumOfN2(1000000) )


    

    




Sum is 500000500000 required  0.0971889 seconds 
Sum is 500000500000 required  0.0589759 seconds 
Sum is 500000500000 required  0.0463891 seconds 
Sum is 500000500000 required  0.0411401 seconds 
Sum is 500000500000 required  0.0398369 seconds 

In [15]:

    

def sumOfN3(n):
    start=time.time()
    theSum = (n*(n+1))/2
    end=time.time()
    return theSum, end-start

print(sumOfN3(10))


    

    




(55, 1.9073486328125e-06)

In [17]:

    

for i in range(5):
    print("Sum is %d required %10.7f seconds " % sumOfN3(10000*10**(i)) )


    

    




Sum is 50005000 required  0.0000019 seconds 
Sum is 5000050000 required  0.0000010 seconds 
Sum is 500000500000 required  0.0000012 seconds 
Sum is 50000005000000 required  0.0000010 seconds 
Sum is 5000000050000000 required  0.0000010 seconds 

In [28]:

    

def findmin(X):
    start=time.time()
    minval= X[0]
    for ele in X:
        if minval > ele:
            minval = ele
    end=time.time()
    return minval, end-start


    

In [29]:

    

def findmin2(X):
    start=time.time()
    L = len(X)
    overallmin = X[0]
    for i in range(L):
        minval_i = X[i]
        for j in range(L):
            if minval_i > X[j]:
                minval_i = X[j]
        if overallmin > minval_i:
            overallmin = minval_i
    end=time.time()
    return overallmin, end-start


    

In [21]:

    

import random


    

In [30]:

    

for i in range(5):
    print("findmin is %d required %10.7f seconds" % findmin( [random.randrange(1000000) for _ in range(10000*10**i)] ) )


    

    




findmin is 2 required  0.0005572 seconds
findmin is 9 required  0.0026450 seconds
findmin is 0 required  0.0234010 seconds
findmin is 0 required  0.2041671 seconds
findmin is 0 required  2.0520091 seconds

In [31]:

    

for i in range(5):
    print("findmin2 is %d required %10.7f seconds" % findmin2( [random.randrange(1000000) for _ in range(10000*10**i)] ) )


    

    




findmin2 is 125 required  3.4158430 seconds
findmin2 is 6 required 332.1417611 seconds






    




---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-31-45329949d42b> in <module>()
      1 for i in range(5):
----> 2     print("findmin2 is %d required %10.7f seconds" % findmin2( [random.randrange(1000000) for _ in range(10000*10**i)] ) )

<ipython-input-29-4a28846f5efc> in findmin2(X)
      5     for i in range(L):
      6         minval_i = X[i]
----> 7         for j in range(L):
      8             if minval_i > X[j]:
      9                 minval_i = X[j]

KeyboardInterrupt: 

In [34]:

    

def anagramSolution(s1,s2):
    """ @fn anagramSolution
        @details 1 string is an anagram of another if the 2nd is simply a rearrangement of the 1st
                    'heart' and 'earth' are anagrams
                    'python' and 'typhon' are anagrams
    """
    A = list(s2) # Python strings are immutable, so make a list
    pos1 = 0 
    stillOK = True
    while pos1 < len(s1) and stillOK:
        pos2 = 0 
        found = False
        while pos2 < len(A) and not found:
            if s1[pos1] == A[pos2]:  # given s1[pos1], try to find it in A, changing pos2
                found = True
            else:
                pos2 = pos2+1
        
        if found:
            A[pos2] = None
        else:
            stillOK = False
        pos1 = pos1 + 1
    return stillOK


    

In [35]:

    

anagramSolution("heart","earth")


    

    
Out[35]:





True

In [36]:

    

anagramSolution("python","typhon")


    

    
Out[36]:





True

In [37]:

    

anagramSolution("anagram","example")


    

    
Out[37]:





False

In [ ]:

    

def anagramSolution2(s1,s2):