Question

public void printQueue(DoublyLinkedQueue<Integer> Q){

int len = Q.size();

int k = 0;

for (int i=0; i < len; ++i){

k = Q.dequeue();

Q.enqueue(k);   

System.out.println(Q.dequeue());

}

}

What is the complexity of this code?

Select one:

a. O(N), N = k

b. Q(1)

c. Q(N2), N = Q.size()

d. O(M), M = Q.size()

e. None of the alternatives is correct.

which one?

Answer 1

Given code is :

1 public void printQueue(DoublyLinkedQueue<Integer> Q){

2 int len = Q.size();

3 int k = 0;

4 for (int i=0; i < len; ++i){

5 k = Q.dequeue();

6 Q.enqueue(k);   

7 System.out.println(Q.dequeue());

8 }

9 }

Lets analyze line by line

First line initializes a function with name printQueue that takes a doublyLinkedList

second line initializes len=size of the queue

third line initializes k=0

fourth line declares a for loop which runs from 0 to len of queue

fifth line k=dequeue first element of the queue which can be done in O(1) time since the queue has front pointer

sixth line enqueue the dequeued element into the list which can be done in O(1) time since the queue has rear pointers

seventh line dequeue an element from the queue and prints it to the screen which is done in O(1) time since the queue front pointer

eight and ninth line closes the loop

Now, thing to note is apart from the for loop everything takes O(1) time so the time complexity of the function will depend on the for loop

the loop runs from 0 to length of the queue so the time complexity will be O(length(queue))

according to the options

a. O(N), N = k

b. Q(1)

c. Q(N2), N = Q.size()

d. O(M), M = Q.size()

e. None of the alternatives is correct.

d is the correct answer

O(M) where M is the queue size

example run of the program for 1,2,3,4 queue

1st iteration

print 2 , queue remaining 3,4,1

2nd iteration

print 4 , queue remaining 1,3

3rd iteration

print 3 , queue remaining 1

4th iteration

print 1 ,queue empty

output

2

4

3

1