About 3 hours
While computers are lightning fast, some code can run faster than other code. When computer programs get larger and larger, a slow runtime can be noticeable to the user. Luckily, code can be written in efficient ways. Understanding runtime complexity is important for multiple reasons:
Which companies use runtime complexity? Pinterest reported that search engine traffic and sign-ups increased by 15% when the perceived load times decreased by 40%. While there are many factors that contribute to the waiting time of large websites, any company will want their programmers to be considering runtimes when writing their code.
Google also has written extensively on the importance of runtime, and why more efficient websites lead to increased web traffic.
Participants will be able to:
There are several common runtimes that you should understand:
Indexing into an array (e.g. array[7]) is O(1)
Looking up a key in an object (e.g. object["name"]) is O(1)
Sorting an array (with a fast algorithm) is O(n log n) – this isn’t simple to prove, but if you’re
curious you can read more about why here and here
Big-O/runtime describes the worst case scenario runtime. For example, if you’re looking at each item in a list to find a specific element, the best case scenario is if it’s the first element and you find it right away! But the worst case is if you look through every single item, and the one you are looking for is the last item in the list or not in the list at all. Runtime analysis focuses on the worst-case scenario.
Only the largest/fastest-growing term matters. For example, if a function takes n^2 + 3n steps,
the function is O(n^2), because the runtime will be dominated by the n^2 term
When stating the runtime complexity, drop any constants. For example, if a function takes 4n
steps, we drop the 4 and call it O(n). This is because runtime complexity describes
how the time of the function grows with relation to the input – not the exact time it takes to run.
These things are not covered in this lesson, but they are related and important to know.
Different data structures let you do different things quickly. So far you’ve learned about two data structures: arrays and objects. Later, you’ll learn about more data structures, including linked lists, trees, stacks, and queues. You’ll learn about the runtime complexity of doing different operations with these data structures.
Space complexity. Similar to time complexity, algorithms can use differing amounts of memory
Runtime complexity is related to (but not the same!) as the total amount of time it takes to run a piece of code. A piece of O(n^2) code could run faster than a piece of O(n) code.
Techtonica staff will assign pairs.
Runtime Complexity Exercise 1: Reading code and analyzing runtime
Read the functions in runtime1-analyzing.js. For each function, figure out:
Runtime Complexity Exercise 2: Comparing code
Compare multiple pieces of code that do the same thing, and figure out the runtime of each one. Which solution would be fastest for large input sizes? runtime2-comparisions.js
Runtime Complexity Exercise 3: Solving problems and writing code
How would you solve these problems runtime3-solving.md? Can you think of an O(n^2), O(n log n), O(n) solution?
Discuss with the group and an instructor:
How important is it to understand runtime complexity?
What is Big-O/runtime?
What others names to Runtime complexity that are generally used interchangeably?
-Make a cheat sheet about runtime complexity. For O(1), O(log(n)), O(n), and O(nlogn) and O(n^2), give an example of 1-3 algorithms/operations that have this runtime.