Time & Space Complexity

Question 1

Horrible to Excellent Complexity

Answer 1

Question 2

Binary Search in a sorted array of N elements

Answer 2

O(log N)

Question 3

Reversing a string of N elements

Answer 3

O(N)

Question 4

Linear search in an unsorted array of N elements

Answer 4

O(N)

Question 5

Compare two strings with lengths L1 and L2

Answer 5

O(min(L1,L2))

Question 6

Computing the Nth Fibonacci number using dynamic programming

Answer 6

O(N)

Question 7

Checking if a string of N characters is a palindrome

Answer 7

O(N)

Question 8

Finding a string in another string using the Aho-Corasick algorithm

Answer 8

O(N)

Question 9

Sorting an array of N elements using Merge Sort/Quick Sort/Heap Sort

Answer 9

O(N ∗ log N)

Question 10

Sorting an array of N elements using Bubble sort

Answer 10

O(N^2)

Question 11

Two nested loops from 1 to N

Answer 11

O(N^2)

Question 12

The Knapsack problem of N elements with capacity M

Answer 12

O(N*M)

Question 12

Finding a string in another string – the naive approach

Answer 12

O(L1*L2)

Question 13

Three nested loops from 1 to N

Answer 13

O(N^3)

Question 14

Twenty-eight nested loops … you get the idea

Answer 14

O(N^28)

Question 15

Generating all subsets of a set of N elements

Answer 15

O(2^N)

Question 16

Adding a value to the top of a stack

Answer 16

O(1)

Question 17

Removing the value at the front of the queue

Answer 17

O(1)

Question 17

Adding a value to a hash

Answer 17

O(1)

Question 18

Checking if a value is in a hash

Answer 18

O(1)

Question 18

Removing the value at the top of a stack

Answer 18

O(1)

Question 19

Adding a value to end of the queue

Answer 19

O(1)

Question 20

Reversing a stack

Answer 20

O(N)

Question 21

Reversing a queue

Answer 21

O(N)

Question 22

Adding a value to the heap

Answer 22

O(logN)

Question 23

Removing the value at the top of the heap

Answer 23

O(logN)