## Introduction

Time complexity and bit-wise operations are the two main concepts one needs to learn when programming. **Time complexity **is the measure of the time taken by the processor to run a piece of code, and **bit-wise operations** are the operations done on the bits of a number.

## Questions

**1. What is the output of the following code snippet for arr[] = {****9, 12, 2, 11, 2, 2, 10, 9, 12, 10, 9, 11, 2}****?****int fun(int arr[], int n)****{**** int x = arr[0];**** for (int i = 1; i < n; i++)**** x = x ^ arr[I];**** return x;**

**}**

A. 10

B. 8

C. 7

D. 9

**Solution**: (D). The above code is taking the XOR of all the elements of the array arr. Thus, the answer will be 9.

**2. What is the following expression doing? **** x = (x<<1) + x + (x>>1)**

A. Multiplying an integer with 5

B. Multiplying an integer with 2

C. Multiplying an integer with 3.5

D. Multiplying an integer with 0.5

**Solution**: (C). If the integer is 4, it becomes 15. If itâ€™s 5, it gives 17. Thus, you can check for any integer, youâ€™ll know that the expression multiplies it by 3.5

**3. What is the following expression doing?****x = x & (x-1)**

A. Turns off the rightmost set bit

B. Turns off the leftmost set bit

C. Turns all bits equal to 0

D. Turns all bits equal to 1

**Solution**: (A). After checking for any integer, we can conclude this.

**4. The time complexity of Bellman-Ford single-source shortest path algorithm for a complete graph of n vertices is?**

A. O(n^2)

B. O((n^2)*logn)

C. O(n^3)

D. O((n^3)*logn)

**Solution**: (C).

**5. The number of comparisons made in the worst case to search an element in a linked list is?**

A. n/2

B. logn

C. n

D. logn - 1

**Solution**: (C). In the worst case, we might need to check all the elements one by one. Thus, the complexity can be O(n).

**6. If we need to concatenate two linked lists in O(1) time, which of the following lists should be used?**

A. Singly linked list

B. __Doubly Linked List__

C. Circular doubly linked list

D. Array implementation of list

**Solution**: (C). Circular doubly linked list will not require any traversal for concatenation.

**7. Place the following time complexities in increasing order of value.****F1 = n^2, F2 = n^(3/2), F3 = n*(log _{2}n), F4 = n^(log_{2}n)**

A. F3, F2, F1, F4

B. F3, F2, F4, F1

C. F2, F3, F1, F4

D. F2, F3, F4, F1

**Solution**: (B). is the correct order because F3<F2<F4<F1

**8. What is the time complexity of the euclidean GCD method?**

A. O(n)

B. O(nlog_{2}n)

C. O(log_{2}n)

D. O(n^2)

**Solution**: (C). The __euclidean GCD__ method makes log_{2}n comparisons. Thus, the time complexity is O(log_{2}n).

**9. What is the time complexity of the following code:****int f(n){**** if(n==1){**** return 1;**** }****return f(n-1)+f(n-1);****}**

A. O(n)

B. O(logn)

C. O(n^2)

D. O(2^n)

**Solution**: (D). There will be 2^n calls made. Thus, the time complexity is O(2^n).

**10. âˆ‘O(n) where, k is varying from 1<=k<=n, where O(n) stands for order n is:**

A. O(n)

B. O(n^2)

C. O(k^3)

D. O(3*(n^2))

**Solution**: (B). n time order n will be O(n*n) = O(n^2).

Read More - __Time Complexity of Sorting Algorithms__