Skip to content

Instantly share code, notes, and snippets.

@Audhil
Last active October 27, 2017 17:01
Show Gist options
  • Save Audhil/fb5f8278de0c9dc679cf1eeaa56d6fd7 to your computer and use it in GitHub Desktop.
Save Audhil/fb5f8278de0c9dc679cf1eeaa56d6fd7 to your computer and use it in GitHub Desktop.
Big O notation & Logrithms
##Big O notations - of algorithms
Big O describes the worst case scenario, can be used to define execution time or space used (e.g. in memory or on disk) by an algorithm.
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(1)
executes in same time or space regardless of size of the input data
vals = [None,'jack','and','jill']
def is_first_element_null(ds):
return ds[0] is None
print(is_first_element_null(vals))
# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(N)
O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
vals = [None, 'jack', 'and', 'jill']
def contains_value(ds, value):
for val in ds:
if val == value:
return True
return False
print(contains_value(vals, 'jill'))
# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(N^2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N^3), O(N^4) etc.
vals = [None, 'jack', 'and', 'jill', 'jack']
def contains_duplicates(ds):
for outer_id, outer_value in enumerate(ds):
for inner_id, inner_value in enumerate(ds):
if outer_id == inner_id:
continue
if ds[outer_id] == ds[inner_id]:
return True
return False
print(contains_duplicates(vals))
# O/P
True
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
O(2^N)
O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2N) function is the recursive calculation of Fibonacci numbers:
def fibonacci(number):
if number <= 1:
return number
return fibonacci(number - 2) + fibonacci(number - 1)
print(fibonacci(20))
# O/P
6765
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
##Logrithms
O(log N)
Binary Search Algorithm
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
more info on :
http://bigocheatsheet.com/
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment