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*(log2n), F4 = n^(log2n)
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(nlog2n)
C. O(log2n)
D. O(n^2)
Solution: (C). The euclidean GCD method makes log2n comparisons. Thus, the time complexity is O(log2n).
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