- Read the following article on Big O: Big O Notation & Complexity in Ruby
- Work through this quiz on Big O. Try out the code snippets and read the answers.
- Do the assignment below and submit a PR with your answers.
Give the efficiency of each of the following code snippets
Snippet EX - Big O: Answer given for this first example: O(n^2)
+ rainbow.each do |item|
+ item.each do |key, value|
+ puts Rainbow(key.to_s).color(value[:r], value[:g], value[:b])
+ end
+ endSnippet 1 - Big O: O(n)
+def print_rainbow(array)
+ array.each do |element| ###n from the .each loop
+ color = element.keys
+ color_string = color[0].to_s
+ puts color_string.colorize(color[0]) ###is colorize a loop??
+ end
+endSnippet 2 - Big O: O(1)
+ def lose?
+ if @number_of_guesses == 0
+ puts "The dinosaur chomps you before you are able to guess the word, '#{ @answer_validation_array.join("") }'."
+ puts "You were eaten :("
+ return true
+ else
+ return false
+ end
+ endSnippet 3 - Big O: O(n^2)
+ def draw_guesses
+ # split word and put letters in array
+ until @letter_array.length == @word.length
+ @word.split("").each do |letter| ###n from each loop
+ @letter_array.push(letter)
+ end
+ word_length = @letter_array.length
+ word_length.times do
+ @dashes_array.push("_ ")
+ end
+ end
+ @dashes_array.each do |dash| ###n from each loop
+ print dash
+ end
+ # draws blank spaces or correct guesses under ice cream
+ endSnippet 4 - Big O: O(n^2)
def overall_mood(entries)
return nil if entries.length == 0
emoticons = Hash.new(0)
entries.each do |entry| ###n from each loop
emoticon = analyze_mood(entry) ###n from each loop in anaylze_mood
emoticons[emoticon] += 1
end
return emoticons.max_by{|k,v| v}[0]
endSnippet 5 - Big O: O(n^3)
+def overall_mood
+ all = {
+ positive: 0,
+ negative: 0,
+ meh: 0
+ }
+ text.each do |aline| ###n from each loop
+ line = strip_punctuation(aline)
+ face = analyze_mood(line) ###n from analyze_mood
+ if face == ":-)"
+ all[:positive] +=1
+ if face == ":-("
+ all[:negative] +=1
+ else
+ all[:meh] +=1
+ end
+ end
+ largest = all.max_by{|key, value| value} ###n from max_by
+ puts "#{largest.keys} is most common mood"
+endSnippet 6 - Big O: O(n^2)
+def overall_mood(array)
+ happy_moods = []
+ sad_moods = []
+ neutral_moods =[]
+ array.each do |line| ###n from each loop
+ moods = analyze_mood(line) ###n from analyze_mood
+ if moods == ":-)"
+ happy_moods << moods
+ elsif moods == ":-("
+ sad_moods << moods
+ else
+ neutral_moods << moods
+ end
+ end
+ happy_length = happy_moods.length
+ sad_length = sad_moods.length
+ neutral_length = neutral_moods.length
+
+ if happy_length > sad_length && happy_length > neutral_length
+ return "The most common mood is :-)"
+ elsif sad_length > happy_length && sad_length > neutral_length
+ return "The most common mood is :-("
+ else
+ return "The most common mood is :-|"
+ end
+endSnippet 7 - Big O: O(n)
for j in 2..num.length
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
endSnippet 8 - Big O: O(n^2)
n.times do |i| ###n from times loop
index_min = i
(i + 1).upto(n) do |j| ###n from upto
index_min = j if a[j] < a[index_min]
end
# Yep, in ruby I can do that, no aux variable. w00t!
a[i], a[index_min] = a[index_min], a[i] if index_min != i
endSnippet 9 - Big O: O(n^2)
public int[] sort(int[] toSort) {
for (int i = 0; i < toSort.length -1; i++) { //n from for loop//
boolean swapped = false;
for (int j = 0; j < toSort.length - 1 - i; j++) { //n from for loop//
if(toSort[j] > toSort[j+1]) {
swapped = true;
int swap = toSort[j+1];
toSort[j + 1] = toSort[j];
toSort[j] = swap;
}
}
if(!swapped)
break;
}
return toSort;
}Snippet 10 - Big O: O(n^2)
import java.util.Random;
public class GoBozo {
public static void main(String args[]) {
int[] arMyValues = { 3, 2, 1, 5, 4 };
BozoSort(arMyValues);
System.out.println("Array sorted... you bozo!");
// Loop through the array and show it sorted.
for (int i = 0; i < 5; i++) //n from for loop//
System.out.println("Element: " + i + " - " + arMyValues[i]);
}
}
// BozoSort Algorithm
// Warning: Highly inefficient and not recommended for large arrays.
// Use with caution, it is for bozos after all!
private static void BozoSort(int[] arValues) {
int slot1 = 0;
int slot2 = 0;
int temp;
Random rand = new Random();
// Continue until sorted
while (!isSorted(arValues)) {
// Pick two values at random.
slot1 = rand.nextInt(arValues.length);
slot2 = rand.nextInt(arValues.length);
// Swap the values and go for a retest.
temp = arValues[slot1];
arValues[slot1] = arValues[slot2];
arValues[slot2] = temp;
}
}
// Loop through the array and determine if one value is larger
// than the one after it. If it is, then it isn't sorted.
// Returns true if the array is sorted.
private static boolean isSorted(int[] arValues) {
for (int i = 0; i < arValues.length - 1; i++) { //n from for loop//
if (arValues[i] > arValues[i + 1]) {
return false;
}
}
return true;
}
}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent