Giter Club home page Giter Club logo

big-o's Introduction

Evaluating Efficiency

  1. Read Big O Notation for Newbies with Ruby
  2. Work through this quiz on Big O. Try out the code snippets and read the answers.
  3. Do the assignment below and submit a PR with your answers.

Assignment - Determine the big O

Give the efficiency of each of the following code snippets.

Examples

Examples

Problems for you

Snippet 1 - Big O:

def largest?(array, value)
  array.each do |item|
    return false if item > value
  end
  return true
end

Snippet 2 - Big O: O(n) - Linear. This code will iterate through a hash of customers twice. Runtime dependent on number of key-value pairs in hash.

def info_dump(customers)
  puts "Customer Names: "
  customers.each do |customer|
    puts "#{customer[:name]}"
  end
  puts "Customer Locations: "
  customers.each do |customer|
    puts "#{customer[:country]}"
  end
end

Snippet 3 - Big O: O(1) - Constant. Returns a boolean regarding the first element of an array. Runtime is the same no matter the length of the array.

def first_element_is_red?(array)
  array[0] == 'red' ? true : false
end

Snippet 4 - Big O:

def duplicates?(array)
  array.each_with_index do |item1, index1|
    array.each_with_index do |item2, index2|
      next if index1 == index2
      return true if item1 == item2
    end
  end
  false
end

Snippet 5 - Big O: O(n^2) - Quadratic. Iterates through one array. For each element of the array, iterates through a second array. Runtime is dependent on length of first array times length of second array.

words = [chocolate, coconut, rainbow]
endings = [cookie, pie, waffle]

words.each do |word|
  endings.each do |ending|
    puts word + ending
  end
end

Snippet 6 - Big O: O(n) - Linear. Runs through the array one time. Runtime dependent on length of array.

numbers = [1,2,3,4,5,6,7,8,9,10]

def print_array(array)
    array.each {|num| puts num}
end

Snippet 7 - Big O: Big O: O(n^2) - Quadratic

# this is insertion sort
(2..num.length).each do |j|
    key = num[j]
    i = j - 1
    while i > 0 and num[i] > key
        num[i+1] = num[i]
        i = i - 1
    end
    num[i+1] = key
end

Snippet 8 - Big O: O(n^2) - Quadratic

# this is selection sort
n.times do |i|
  index_min = i
  (i + 1).upto(n) do |j|
    index_min = j if a[j] < a[index_min]
  end
  a[i], a[index_min] = a[index_min], a[i] if index_min != i
end

big-o's People

Contributors

alyssahursh avatar sudocrystal avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.