Big-O Notation Interview Questions and Answers

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:

Say we have an array of n elements:

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:

x = array[0];

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:

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:

[1]->[2]->[3]
Push 5:
[5]->[1]->[2]->[3]
Pop:
[1]->[2]->[3]
// returning 5

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(
n2) ). 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.

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:
[1]->[2]->[3]
Push 5:
[5]->[1]->[2]->[3]
Pop:
[1]->[2]->[3]
// returning 5

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.

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:

O(
n2) means for every element, you're doing something with

every other element, such as comparing them. Bubble sort is an example of this.

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.

O(
ck) - exponential time complexity algorithms are, for example, brute-force search and traveling salesman
problems.

An example may be if you had a set of characters of length c , and have the password of length k . Then you would need a

O(
ck) time to break the password, like
O(
10n) is trying to break a password by testing every
possible combination (assuming
numerical password of length n ).

**
O(
1) time **
Accessing Array Index ( int a = ARR[5]; )

Inserting a node in Linked List Pushing and Poping on Stack Insertion and Removal from Queue Finding out the parent or left/right child of a node in a tree stored in Array Jumping to Next/Previous element in Doubly Linked List

O(
n) time

In a nutshell, all Brute Force Algorithms, or Noob ones which require linearity, are based on

O(
n) time
complexity
Traversing an array
Traversing a linked list
Linear Search
Deletion of a specific element in a Linked List (Not sorted)
Comparing two strings
Checking for Palindrome

Counting/Bucket Sort and here too you can find a million more such examples....

O(
log n) time
Binary Search
Finding largest/smallest number in a binary search tree

Certain Divide and Conquer Algorithms based on Linear functionality

Calculating Fibonacci Numbers - Best Method The basic premise here is NOT using the complete data, and reducing the problem size with every iteration

O(
n log n) time

The factor of 'log n' is introduced by bringing into consideration Divide and Conquer. Some of these algorithms are the best optimized ones and used frequently. Merge Sort Heap Sort Quick Sort Certain Divide and Conquer Algorithms based on optimizing

O(
n2) algorithms
O(
n2) time

These ones are supposed to be the less efficient algorithms if their

O(
n log n) counterparts are present. The

general application may be Brute Force here. Bubble Sort Insertion Sort Selection Sort Traversing a simple 2D array

O(
n!) an algorithm that "tries everything," since there are (proportional to) n! possible combinations of n
elements that might solve a given problem. It means to do something for all possible permutations (possible
ways in which a set or number of things can be ordered or arranged) of the N elements. Traveling salesman is

an example of this, where there are N! ways to visit the nodes, and the brute force solution is to look at the total cost of every possible permutation to find the optimal one.

Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time, but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes at least n log n (Omega n log n) and no more than n log n (Big O n log n).

Problem

Consider this code:

for(int i = 0; i < n; i++){
  for(int j = i; j < n; j++){
    array[j] += 2;
  }
}

What is complexity of this code snippet?

Solution

This is

O(
n2) (or Quadratic complexity) since for each pass of the outer loop (
O(
n) ) we have to go through

the entire list again so the n's multiply leaving us with n squared.

If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else. A common example is the dynamic array. If we have already allocated memory for a new entry, adding it will beO(

1. . If we haven't allocated it we will do so by allocating, say, twice the current amount. This particular insertion will not be

O(
1) , but rather something else.

What is important is that the algorithm guarantees that after a sequence of operations the expensive operations will be amortised and thereby rendering the entire operation

O(
1) .

An algorithm is a method for computing the value of a **mathematical function **-- maths functions are a mapping from one input to an output. And more technically: An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.

Big O notation in this context is being used to describe a relationship between the size of the input of a function and the number of operations that need to be performed to compute the result (output) for that input. That operation has no input that the output can be related to, so using Big O notation is nonsensical. The time that the operation takes is independent of the inputs of the operation (which is...none). Since there is no relationship between the input and the number of operations performed, you can't use Big O to describe that non-existent relationship. Even worse; this isn't technically an algorithm. An algorithm is a method for computing the value of a mathematical function -- maths functions are a mapping from one input to an output. Since this takes no input and returns nothing, it's not a function, in the mathematical sense.

Because you are usually just interested in the worst case when analyzing the performance. Thus, knowing the upper bound is sufficient. When it runs faster than expected for a given input - that is ok, it's not the critical point. It's mostly negligible information. Some algorithms don't have a tight bound at all. See quicksort for example which is

O(
n2) and
Omega(n) .

Moreover, tight bounds are often more difficult to compute.

By reading a book you are effectively traverse it (by visiting every page at least once) so it is

O(
n)

Space complexity means the amount of space the algorithm needs to run. Example 1: Sorting-Algorithms All sorting algorithms need at least O(n) space to save the list (of length n ) they have to sort 1.

Bubblesort (and most other sorting algorithms too) can work

in-place, this means that it needs no more space as it needs to save the list. (just searching two elements in the wrong order and swaping them) 2. Stupid-Sort lists all permutations of the input list (and saves them) and then searching the sorted one. Since there are n! permutations this algorithm needs O(n * n!) space. Example 2: Number representation A number n can be saved in different ways:

1. binary (or any other base ≥2 ): this needs O(log n) space, due to n = 2log n
2. unary: here you write n as a sum of ones ( n = 1 + 1 + 1 + ... + ... + 1 ) and you have to save every one. So this needs O(n) space, due to n = n ⋅ 1 .

In many cases the "O" of an algorithm will fall into one of the following cases:O(

1. • Constant complexity. Time to complete is the same regardless of the size of input set. An example is accessing an array element by index. 1 item: 1 second 10 items: 1 second 100 items: 1 second

O(
log n) - Logarithmic complexity. Time to complete increases roughly in line with the log (n). For
example 1024 items takes roughly twice as long as 32 items, because Log2(1024) = 10 and Log2(32) = 5. An

example is finding an item in a binary search tree (BST). 1 item: 1 second 10 items: 2 seconds 100 items: 3 seconds 1000 items: 4 seconds 10000 items: 5 seconds

O(
n) - Linear complexity. Time to complete that scales linearly with the size of the input set. In other

words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example is counting the number of items in a linked list. 1 item: 1 second 10 items: 10 seconds 100 items: 100 seconds

O(
n log n) - Time to complete increases by the number of items times the result of Log2(N). An example of

this is heap sort and quick sort.

O(
n2) - Quadratic complexity. Time to complete is roughly equal to the square of the number of items. An

example of this is bubble sort. 1 item: 1 second 10 items: 100 seconds 100 items: 10000 seconds

O(
n!) - Time to complete is the factorial of the input set. An example of this is the traveling salesman
problem brute-force solution.