The ultimate guide to Big-O notation for coding interviews, developed by FAANG engineers. Learn algorithm complexity in simple terms and get interview-ready in just a few hours.

This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond

## Question 1
Kim is new to programming and designs the following hash function for her hash table.

```java
    int computeHash(int key) {
        int hash = 0;
        for (int i = 1; i <= key; i++) {
            hash += i;
        }
        return hash;
    }
```

**a-** What is the time complexity of the hash function?

**b-** Can we make the hash function take constant time?

**c-** What is the space requirements/complexity if Kim chooses to stick with her hash function and wants to ensure no collisions happen?

> **Note:** The solution to the following questions is not provided in the next lesson. These questions are just for the user to solve by themselves.


## Question 2
We talked about one-dimensional arrays. How would the complexity of accessing an element be affected in a 2-dimensional array?


## Question 3
We have a class called N-Dimensional Array. The class takes in a parameter *n* and creates an n-dimensional array. What would be the time complexity of accessing the elements of the array in the nth dimension?

# Question 1
Kim is new to programming and designs the following hash function for her hash table.

```java
    int computeHash(int key) {
        int hash = 0;
        for (int i = 1; i <= key; i++) {
            hash += i;
        }
        return hash;
    }
```

**a-** What is the time complexity of the hash function?

**b-** Can we make the hash function take constant time?

**c-** What is the space requirements/complexity if Kim chooses to stick with her hash function and wants to ensure no collisions happen?

> **Note:** The solution to the following questions is not provided in the next lesson. These questions are just for the user to solve by themselves.


# Question 2
We talked about one-dimensional arrays. How would the complexity of accessing an element be affected in a 2-dimensional array?


# Question 3
We have a class called N-Dimensional Array. The class takes in a parameter *n* and creates an n-dimensional array. What would be the time complexity of accessing the elements of the array in the nth dimension?

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Problem Set 4

Question 1