Day 5: Big O Set Quiz

In this quiz we'll ask you to calculate the time complexity for several of the MySet class methods. Remember that we used a Hash/Object as the underlying data structure for our class. If you don't know the time complexity for a method, you may need to Google.

1. Mult choice

Calculate the time complexity for the following method:

JavaScript

constructor(iterable) {
  if (!(iterable === undefined || 
    Array.isArray(iterable) || 
    typeof iterable === 'string')) {
      throw new Error('MySet only accepts iterables or nothing on initialization!');
  }
this.data = {};
if (iterable) {
for (const el of iterable) {
this.data[el] = true;
}
}
}

Ruby

def initialize(iterable = nil)
  raise 'MySet only accepts iterables or nothing on initialization!' unless 
    iterable.nil? || iterable.kind_of?(Array) || iterable.kind_of?(String)
@data = {}
unless iterable.nil?
items = iterable.kind_of?(String) ? iterable.split('') : iterable
items.each { |el| @data[el] = true }

end
end



O(n): Linear time

Correct! The worst case is if an Array or String is provided as an argument. In that case, we iterate over the input and add each item to data, which is a linear-time operation.


O(1): Constant time

Not quite. This would be true if the Array or String were always the same length, but an Array or String of any length could be provided.


I don't know

With time and practice, it'll start to sink in. Keep studying and you'll get there.




Mult choice

Calculate the time complexity for the following method:
JavaScript

add(item) {
  this.data[item] = true;
  return this;
}


Ruby

def add(item)
  @data[item] = true
  self
end



O(1): Constant time

Perfect! Accessing a value by key in a Hash/Object takes constant time, so does returning the instance.


O(2): Constant time

Not quite. Remember that we have to simplify our notation, so constant time is always expressed as O(1), even if we perform many constant-time operations.


O(n): Linear time

Not quite. You may wish to look up Big O for accessing values by key in a Hash.


I don't know

With time and practice, it'll start to sink in. Keep studying and you'll get there.




Mult choice

Calculate the time complexity for the following method:
JavaScript

has(item) {
  return !!this.data[item];
}


Ruby

def has(item)
  !!@data[item]
end



O(1): Constant time

Yes! Accessing a value by key takes constant time.


O(n): Linear time

Not quite. What is Big O for accessing a value by key in a Hash or Object?


I don't know

With time and practice, it'll start to sink in. Keep studying and you'll get there.