Top 22 Big-O Notation Interview Questions And Answers

Q: What is complexity of this code snippet?

This would be O ( n ) since at most we would have to look through the entire list to find our number. The Big-O is still O ( n ) even though we might find our number the first try and run through the loop once because Big-O describes the upper bound for an algorithm.

Q: What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

O ( 1 ) . Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Q: What the heck does it mean if an operation is O ( log n ) ?

** O ( log n ) ** means for every element, you're doing something that only needs to look at **log N** of the elements. This is usually because you know something about the elements that let you make an _efficient choice_ (for example to reduce a _search space_). The most common attributes of logarithmic running\-time function are that: * the choice of the next element on which to perform some action is one of several possibilities, and * only one will need to be chosen or * the elements on which the action is performed are digits of `n` Most efficient sorts are an example of this, such as **merge sort**. It is `O(log n)` when we do divide and conquer type of algorithms e.g binary search. Another example is **quick sort** where each time we divide the array into two parts and each time it takes `O(N)` time to find a pivot element. Hence it `N O(log N)` Plotting `log(n)` on a plain piece of paper, will result in a graph where the rise of the curve decelerates as `n` increases: ![](https://i.stack.imgur.com/qPNNp.png)

Q: What is the big O notation of this function?

It is simply O ( n ) . When you have a composite of multiple parts in Big O notation which are added, you have to choose the biggest one. In this case it is _`O(3n)`_, but there is no need to include constants inside parentheses, so we are left with _`O(n)`_.

Q: What exactly would an O ( n 2 ) operation do?

** O ( n 2 ) ** means for every element, you're doing something with _every_ other element, such as comparing them. Bubble sort is an example of this.

Question 1

What is _Big O_ notation?

Accepted Answer

**Big-O** notation (also called "asymptotic growth" notation) is a relative representation of the complexity of an algorithm. It shows how an algorithm *scales* based on input size. We use it to talk about how thing _scale_. Big O complexity can be visualized with this graph:

![](https://i.stack.imgur.com/WcBRI.png)

Question 2

Provide an example of O(1) algorithm

Accepted Answer

Say we have an array of `n` elements: ```cs int array[n]; ``` If we wanted to access the first (or any) element of the array this would be O(1) since it doesn't matter how big the array is, it always takes the same constant time to get the first item: ```cs x = array[0]; ```

Question 3

What is complexity of this code snippet?

Accepted Answer

This would be O(n) since at most we would have to look through the entire list to find our number. The Big-O is still O(n) even though we might find our number the first try and run through the loop once because Big-O describes the upper bound for an algorithm.

Question 4

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Accepted Answer

O(1). Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Question 5

What the heck does it mean if an operation is O(log n)?

Accepted Answer

**O(log n)** means for every element, you're doing something that only needs to look at **log N** of the elements. This is usually because you know something about the elements that let you make an _efficient choice_ (for example to reduce a _search space_). The most common attributes of logarithmic running\-time function are that: * the choice of the next element on which to perform some action is one of several possibilities, and * only one will need to be chosen or * the elements on which the action is performed are digits of `n` Most efficient sorts are an example of this, such as **merge sort**. It is `O(log n)` when we do divide and conquer type of algorithms e.g binary search. Another example is **quick sort** where each time we divide the array into two parts and each time it takes `O(N)` time to find a pivot element. Hence it `N O(log N)` Plotting `log(n)` on a plain piece of paper, will result in a graph where the rise of the curve decelerates as `n` increases: ![](https://i.stack.imgur.com/qPNNp.png)

Question 6

Why do we use Big O notation to compare algorithms?

Accepted Answer

The fact is it's difficult to determine the exact runtime of an algorithm. It depends on the speed of the computer processor. So instead of talking about the runtime directly, we use Big O Notation to talk about _how quickly the runtime grows_ depending on input size. With Big O Notation, we use the size of the input, which we call `n`. So we can say things like the runtime grows “on the order of the size of the input” (O(n)) or “on the order of the square of the size of the input” (O(n²)). Our algorithm may have steps that seem expensive when `n` is small but are eclipsed eventually by other steps as `n` gets larger. For Big O Notation analysis, we care more about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as `n` gets very large.

Question 7

Explain the difference between _`O(1)`_ vs _`O(n)`_ space complexities

Accepted Answer

Let's consider a traversal algorithm for traversing a list. * O(1) denotes _constant_ space use: the algorithm allocates the same number of pointers irrespective to the list size. That will happen if we move (reuse) our pointer along the list. * In contrast, O(n) denotes _linear_ space use: the algorithm space use grows together with respect to the input size `n`. That will happen if let's say for some reason the algorithm needs to allocate 'N' pointers (or other variables) when traversing a list.

Question 8

What is the big O notation of this function?

Accepted Answer

It is simply O(n). When you have a composite of multiple parts in Big O notation which are added, you have to choose the biggest one. In this case it is _`O(3n)`_, but there is no need to include constants inside parentheses, so we are left with _`O(n)`_.

Question 9

What is Worst Case?

Accepted Answer

Big-O is often used to make statements about functions that measure the worst case behavior of an algorithm. **Worst case** analysis gives the maximum number of basic operations that have to be performed during execution of the algorithm. It assumes that the input is in the _worst possible state_ and maximum work has to be done to put things right.

Question 10

What exactly would an O(n²) operation do?

Accepted Answer

**O(n²)** means for every element, you're doing something with _every_ other element, such as comparing them. Bubble sort is an example of this.

Top 22 Big-O Notation Interview Questions

What is Big O notation?

What exactly would an `O(n²)` operation do?

Explain the difference between `O(1)` vs `O(n)` space complexities

Why do we use Big O notation to compare algorithms?

What is Worst Case?

What the heck does it mean if an operation is `O(log n)`?

What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?

Why do we use Big O instead of Big Theta (Θ)?

What is the time complexity for "Hello, World" function?

What is an algorithm?

Name some types of Big O complexity and corresponding algorithms

Explain your understanding of "Space Complexity" with examples

What does it mean if an operation is `O(n!)`?

What is the difference between Lower bound and Tight bound?

What are some algorithms which we use daily that has `O(1)`, `O(n log n)` and `O(log n)` complexities?

Provide an example of `O(1)` algorithm

What is the big O notation of this function?

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

What is complexity of this code snippet?

What is complexity of this code snippet?

What is complexity of "Reading a Book"?

Provide an example of algorithm with time complexity of `O(c^k)`?

Top 22 Big-O Notation Interview Questions

What is Big O notation?

What exactly would an O(n2) operation do?

Explain the difference between O(1) vs O(n) space complexities

Why do we use Big O notation to compare algorithms?

What is Worst Case?

What the heck does it mean if an operation is O(log n)?

What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?

Why do we use Big O instead of Big Theta (Θ)?

What is the time complexity for "Hello, World" function?

What is an algorithm?

Name some types of Big O complexity and corresponding algorithms

Explain your understanding of "Space Complexity" with examples

What does it mean if an operation is O(n!)?

What is the difference between Lower bound and Tight bound?

What are some algorithms which we use daily that has O(1), O(n log n) and O(log n) complexities?

Provide an example of O(1) algorithm

What is the big O notation of this function?

What is complexity of push and pop for a Stack implemented using a LinkedList?

What is complexity of this code snippet?

What is complexity of this code snippet?

What is complexity of "Reading a Book"?

Provide an example of algorithm with time complexity of O(ck)?

What exactly would an `O(n²)` operation do?

Explain the difference between `O(1)` vs `O(n)` space complexities

What the heck does it mean if an operation is `O(log n)`?

What does it mean if an operation is `O(n!)`?

What are some algorithms which we use daily that has `O(1)`, `O(n log n)` and `O(log n)` complexities?

Provide an example of `O(1)` algorithm

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Provide an example of algorithm with time complexity of `O(c^k)`?