Big-O-Smallest-to-Largest

Question 1

1: Constant

Answer 1

O(1)

Question 2

2: Logarithimic

Answer 2

O(log n)

Question 3

3: Linear

Answer 3

O(n)

Question 4

4: Linearithmic

Answer 4

O(n*log n)

Question 5

5: Quadratic

Answer 5

O(n^2)

Question 6

6: Cubic

Answer 6

O(n^3)

Question 7

8: Exponential

Answer 7

O(2^n) or O(e^n), where e > 1

Question 8

9: Factorial

Answer 8

O(n!)

Question 9

7. Quartic

Answer 9

O(n^4)

Question 10

Array/List gets iterated over c * length times. Define Big O

Answer 10

O(n), where is n is the length of array or list

Question 11

How will you identify O(log n)

Answer 11

When number of elements in the problem space gets halved each time.

Question 12

How will you identify O(N^2)/Ouadratic

Answer 12

When we have a single nested loop

for (int i=0; i< n; i++{
for (int j=0; i

Question 13

Find Big O for this

for (int i=0; i

Answer 13

O(nm)

Question 14

Find Big O for this

for (int i=0; i

Answer 14

O(n^2)

Question 15

Find Big O for this

for (int i=0; i

Answer 15

O(n)

Outer loop i is doubled and incremented each time.

Question 16

Find Big O for this

i = //constant
n = //constant
k = //constant
while (i < n){
    i*=k;
    // Statement(s) that take(s) constant time
}

Answer 16

O(log to base K of n)
if K is 2, then O(log n)

Because the loop count is being doubled every time.

Question 17

Find Big O for this
p = 0
for (i = 0; p < n; i++) {
   p = p+i;
   // Statement(s) that take(s) constant time
}

Answer 17

O(sqrt(n))

For loop will run K time, as long as p < n

When ever we see, i getting incremented by its own value, then it will run sqrt of n time.

Question 18

Find Big O for this

for(i = 0; i < n; i++){
  i = i*2;
   // Statement(s) that take(s) constant time
}

And for this
for(i = 0; i < n; i++){
  i = i+2;
   // Statement(s) that take(s) constant time
}

Answer 18

First one: O(log n), as i is doubled every time.

Second one: O(sqrt n), as i is incremented by self every time.

Question 19

Complexity for

Accessing an element in an array

Answer 19

O(1)

Question 20

Complexity for

Traversing an array

Answer 20

O(N)

Question 21

Complexity for

Updating an element in an array

Answer 21

O(1)

Question 22

Complexity for

Inserting an element in the beginning

Answer 22

O(n)

Question 23

Complexity for

Appending an element in the end

Answer 23

Static Array: O(n)

Dynamic Array: Amortized O(1)

Question 24

Complexity for

Inserting an element in the middle

Answer 24

O(n)

Question 25

Complexity for

Removing an element from the middle

Answer 25

O(n)

As we have to shift

Question 26

Complexity for

Removing an element from the end

Answer 26

Static Array: O(n)

Dynamic Array: O(1) as we will update the tail index in Dynamic array

Question 27

Complexity for

Removing an element from the beginning

Answer 27

O(n)

Question 28

Copying an array

Answer 28

O(n)

Question 29

What does Big O try to answer?

Answer 29

It tells us about efficiency of algorithm in terms of time and space, as N - size of input - increases towards infinity.