Big O Notation - Whiteboarding Wednesday

BigO.md

Big O Notation

How can we measure quality of code?

• Readability - How easily can we tell what you were trying to make?
• Time - How long does it take to run?
• Space - How much data do you have to store to run your code?
• Lines of code

Time example

def hi(ary)
  start_time = Time.now 
  ary.each do |x|
    p x 
  end
  end_time = Time.now 
  
  elapsed_time = end_time - start_time 
  p "Function completed in: #{elapsed_time}"
end 

def hi2(ary)
  start_time = Time.now 
  for i in 0..ary.length
     p ary[i]
  end
  end_time = Time.now 
  
  elapsed_time = end_time - start_time 
  p "Function completed in: #{elapsed_time}"
end 

hi([1,2,3,4,5])

hi2([1,2,3,4,5])

Space example

#Option 1 
hi = []

#Option 2 
hi2 = Array.new(5)

Link: https://repl.it/Fl2W/1

What is Big O?

Big O is a way of quantifying of how long methods take to run for a given n, size of input data.

Big O Cheatsheet

http://bigocheatsheet.com/

And change the Understanding Big O section to this:

Understanding Big O

For n of 26, what is the following?

n! =

2^n =

n^2 =

n log n =

n =

log n or 1 =

What do we notice?

• From n! to log n, big O decreases.
• log 26 is approximately equal to 1.3, pretty close to 1!

Big O of built-in methods

[3,2,1].sort
	Big O = n log n 
	
[1, 2, 3].find(2)
	Big O = n 
	
people = {"christian": "caffeine", "jin": "star wars", "andy": "fish", "kat":"hi"}
	people["christian"] 
	Big O = 1
	#hashes have keys 
	
dogs = ["yorkie", "pit bull", "chihuahua"]
	dogs.find("yorkie")
	Big O = n 
	
"look at what the method actually does".split(" ")
	Big O = n
	
continents = ["north america", "south america", "europe", "asia", "africa", "australia", "antarctica"]
	contientes.each do |continent|
		continent.reverse
	end
	Big O = n^2
	

Slides: https://docs.google.com/presentation/d/1KsCcdjA9Ijj3c8ZpCeFZYkXQgG3Fnl1WQwlI__Pjqtg/edit?usp=sharing

Big O

Algorithms: https://classroom.udacity.com/courses/ud513/lessons/7174469398/concepts/71213347930923#

Out of 10,000 interviews, people who did MOOCs...