The Big Ideas Behind Big O Notation

Complexity

Worst Case Scenarios

array = [1,0,0,0,0,0,0,0,0]
def indexOfOne(array)
array.each.with_index do |item,index|
return index if item == 1
end
end
array = [0,0,0,0,0,0,0,0,1]

Inputs

def itemIncreaser(array)
array.each |item| { return item + 1 }
end
def itemConverter(array)
array.each |item| do
item += 1
item += 2
item += 3
return item
end
end

Notation

Example Runtimes

O ( 1 )

def myFunction(array)
doSomethingWith(array[0])
end

O ( N² )

results = []def multiplier(array)
array.each do |x|
array.each do |y|
results.push(x * y)
end
end
end

O ( 2ᴺ )

def doRecursion(input)
return input if input <= 1
return doRecursion(input - 2) + doRecursion(input - 1)
end

O ( log N )

[0,1,3,3,4,5,8,12,15,15,18,21,23,26,30]
^
[0,1,3,3,4,5,8,12                     ]
^
[          5,8,12                     ]
^
[          5                          ]
^

Further Resources

Full stack software developer by day. Writer, illustrator, and general creative dabbler by night.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to set up Raspberry [SSH+GUI]

Recursion — A brief explainer

Introducing Edon

CODE Review April 26th

The Best Advice I Received When I was Stuck in a Programming Rut

Kotlin Basics I

Quick Guides — Wins to SharePoint

Practical Java15 sealed interfaces with design patterns

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Edward Saavedra

Edward Saavedra

Full stack software developer by day. Writer, illustrator, and general creative dabbler by night.

More from Medium

Why did I become a developer?

Programming for fun

THE SORTING AESTHETICS.

What skills make good coder?