TimeComplex 0.0.1

Big O calculations for Time

TimeComplex

This package was created to evaluate functions for time complexity. The function runs an algorithm over and over with randomized input sizes to judge the time complexity. PYPI: https://pypi.org/project/SpaceTimeComplex/

Example

def looper2(n):
    for x in range(n):
        print(x)

def testone(n):
    for x in range(len(n)):
        for y in range(len(n)):
            for z in range(len(n)):
              two = y
              one = x
              three = z

def looper(today,stringer):
    for x in range(today):
        print(x)
    
    for y in stringer:
        print(y)



def logfunc(n):
    for x in range(0,len(n[0]),20):
        print(x) 


def binary_search(array,target):
  low = 0
  high = len(array) - 1
  while low <= high:
    mid = (low + high) // 2 # integer division
    element = array[mid]
    if element == target:
      return mid
    elif element < target:
      low = mid + 1
    else:
      high = mid - 1
  return -1


real = SpaceTimeComplex.RealTime() # Create the class
#x.realTimeComplex(stmt="looper(10)",value=10)

testSet = real.generateTestSet(size2=100) #generate a test set

testSet1 = [[4,"stnr=gwege"], [12,"sagsdgg"], [3,"esfsfsseafesfsefsef"], [45,"stnrefgseege"], [17,"sagwetjtwfwe"], [34,"esfsfssem"],[41,"stn"], [53,"sakhhksdgg"], [24,"esjfjkkfsefsef"], [70,"stnwete"], [7,"sagwefwewsdfsdffwe"] ] 
# format of array. 2d array with each test set inside. You can make your own or just generate one with generateTestSet()

logFunction, SlopeConst = real.complexGuess(testone,testSet) #guess the complexity of a function. Returns the guess and a plot

ratio = real.bestWorst(testone,testSet)

Example of the non-log function graphed using the derived power. $O(n^{2.8})$

This is in respects to time (ms). When accounting for just the growth of input, the input will grow in a polynomial fashion.

Math behind the calculations

A simplistic understanding how the time complexity is extracted stems from the log power rule.

Power Rule:

$log(n^k) = k \cdot log(n)$

After apply a log to both n and y variables, a linear regression is applied.

$y = time, n = input size, b = constant$

$log(y) = log(n^k) + b$

apply the power rule

$log(y) = k \cdot log(n) + b$

Everything can be ignored except for k. k determines the slope of line and tells us the time complexity.

$time complexity = N^k$

Jupyter Lab

The package can also be used in jupyter notebooks.