Class 1 Homework

Practice from today's material

Expression to Big 0

The following expressions represent the amount of time an algorithm takes to run, in terms of the input, N.

What is the Big O runtime complexity of each algorithm?

Example

The following expressions represent the amount of time an algorithm takes to run, in terms of the input, N.

What is the Big O runtime complexity of each algorithm?

Analyzing Code

What is the time complexity of this code sample?

What is the space complexity of this code sample?

var listOfFriends = [];
for (var i = 0; i < N; i++) {
    listOfFriends.push("friend" + i);
}
                

What is the time complexity of this code sample?

What is the space complexity of this code sample?

var firstName = "cat";
var lastName = "dog";
console.log(firstName + lastName);
                

What is the time complexity of this code sample?

What is the space complexity of this code sample?

var listOfFriends = ["dog", "cat", "pig", "goat", "bird"];
var listOfFood = ["pizza", "ramen", "doughnut", "french fries"];

for (var friendIndex = 0; friendIndex < listOfFriends.length; friendIndex++) {
    for(var foodIndex = 0; foodIndex < listOfFood.length; foodIndex++) {
        console.log("I'm giving " + listOfFood[foodIndex] + " to the " + listOfFriends[friendIndex]);
    }
}
                

Prep for next class

In the next class we will be covering search and sort. Some search and sort algorithms have a logorithmic run time or O(logN).

If you would like to review algorithms on your own, you can review them with this Khan Academy video.

Don't worry if this concept is a bit fuzzy, we'll cover the relevant parts in class.