# 2003-GHP Cookie Jar: Hash Tables and Algorithmic Thinking

Put your pending and outstanding questions here 👇
Make the question in H2 tag by using '##'

Example:
## What is JavaScript?

## So my question was "what determines the speed of ONE operation completed by a computer?" I get that time complexity increases the more operations you do (i.e. O(1), O(n), etc), but what determines the speed of just one of those operations (i.e. in a for-loop, checking one value). Is that determined by the speed of light? physical characteristics of the hardware in a computer? Just out of curiosity.

This is one of those: "It depends on.... everything" answer. Basically there are so many different fields that encompass how "fast" something is such as but not limited to:
- computer engineering
- electrical engineering
- mechanical engineering
- materials science
- physics
- computer science
- networking

We can go a bit deeper here:
- Where did you get your computer from?/Who built it?
- Do we know who built the transistors in it?
- How's your internet connection? WiFI? Ethernet? What is that Ethernet cable made of?
- What are your computer's/laptop's hardware specs?
- Have you run the specific program before? Does it have any caching? Does your system have any caching?
- What compiler are you using? Does it optimize?
- Are you running anything else in your computer that may slow it down?

All of this to say this is why we don't measure in absolutes and why we use "Big O" because you can time in milliseconds how fast a function will run but that number will change every time you run it.

[Replit Demo](https://reacttraining.com/react-router/web/example/url-params)
- Press "play" over and over again. The time changes almost every time sometimes drastically.

## How do we create the linkedlist in the hash table to handle collisions? How will we access the values in that case?

We initialize an array as our base structure and each bucket (entry) of the array will contain a linked list. How we handle it is a few ways we noted in the lecture
- Association lists (where it's a custom linked list with a key as well as a pointer to next and the value)
- We can store an array inside of a linked list where index 0 is the key and index 1 is the value
- The last one that we went over is a struct, which is an object (key value pair) that doesn't change once it's initialized

## If two approaches have the same time complexity, which one should you implement?
E.g. Approach 1 = 1 loop = O(n) vs Approach 2 = regex = O(n)

Go with the loop. Easier to look at. Also, depending upon the path the regex takes to match, could take more time. In addition, if the regex is so simple, why use regex? That's like that meme I showed you


For more info on JavaScript Regex, here's an [article](https://medium.com/dailyjs/js-regexp-fast-and-slow-d29d6b77b06)

## Why is the time complexity of accessing a hashmap N/A per Big O Cheat Sheet?
Link: https://www.bigocheatsheet.com/

## Answer

I believe it has to do with the fact that you don't access a hashmap by indexing as you would with an array, for example. Like you can't say, "grab this value at the ith index"

## What is the time complexity of using Set Class methods? The Internet doesn't seem to have an answer :(
Link: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

It depends on the how Set is implemented by the engine. Set is a keyed collection (as opposed to indexed collections like an Array).

But let's think through one case together:
- Set: A collection of unique values
- Array: A collection on non-unique calues
- To add to the back of an array is O(1)
- To add to a Set: It needs to check if what it is about to add will keep the Set unique, which means, it can potentially check the entire Set, which means potentially O(n). However, if the Set is implemented like a keyed collection, then maybe it might use a hashtable under the hood to keep track of stuff, which might mean O(1)

It does depend on the implementation. This would likely warrant a visit to the ECMAScript specifications to know more about how Set is implemented by the engine. Near the bottom of that documentation link you sent is a link to the [spec](https://tc39.es/ecma262/#sec-set-objects). The specs say exactly how each Set method is implemented in pseudocode.

## Why can't O(n+m) just be represented by O(n)?
Here's my train of thought:
1. n is a very large number, m is also large
2. from known examples: O(n+n) = O(2+n) = O(n)
3. n ~ m given how large they are
4. so shouldn't O(n + m) = O(n + n) = O(2n) = O(n)?
Comments: I know it's not that big of a deal, but I just find the presence of an extra variable noisy and confusing so was wondering if I could just simplify O(n+m) into O(n) when explaining to interviewers.

## Answer

I know it's said that we have to think about the input as it gets infinitely large but computing power only goes so far and languages have a threshold of their highest and lowest possible numbers.

Either way, if we know that the two inputs will be different, then it's more complete to present them with two notations, n and m or what have you. The only time it would simplify to O(n) is if the two inputs are the same

## How do you evaluate the time complexity of if/else statements?
Here's my train of thought:
1. if = O(n) (i picked a random n)
2. else = O(n^2) (i picked a random n)
3. is it
a. O(n) + O(n^2) = O(n^2)
b. max(O(n), O(n^2)) = O(n^2) // know it evaluates to the same as (a) but diff way to think about it
c. something else?

## Answer

It's b. Either the if or else will run so it will be the slowest of the two possibilities.