InfyTQ Algorithms Quiz 1

 Although the ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at the first position or at last position.

The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)). Linear search is easier to implement and understand than other searching techniques.

 The Iterative algorithm is faster than the latter as the recursive algorithm has overheads like calling function and registering stacks repeatedly.

In Binary search, the elements in the list should be sorted. It is applicable only for an ordered list. Hence Binary search in the unordered list is not an application.

Since the input array is not sorted, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations

 As the name suggests, the external sorting algorithm uses external memory like tape or disk.

 The modulus q is typically chosen as a prime number that is large enough to reduce the complexity when p is very large.

 

 Euclid’s algorithm is basically used to find the GCD of two numbers. It cannot be directly applied to three or more numbers at a time.

The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n^2) since there are only 7 recursive multiplications and Theta(n^2) scalar additions and subtractions involved for computing the product.

 The correct formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. The function rand() generates random numbers in the range 0 to RAND_MAX.