Prerequisite: Analysis of Algorithms
Options:
Output: 3. O(N + M) time, O(1) spaceExplanation: The first loop is O(N) and the second loop is O(M). Since N and M are independent variables, so we can’t say which one is the leading term. Therefore Time complexity of the given problem will be O(N+M).
Options:
Output: 4. O(N*N)Explanation: The above code runs total no of times = N + (N – 1) + (N – 2) + … 1 + 0 = N * (N + 1) / 2 = 1/2 * N^2 + 1/2 * N O(N^2) times. 3. What is the time complexity of the following code:
Options:
Output: 2. O(nLogn)Explanation: If you notice, j keeps doubling till it is less than or equal to n. Several times, we can double a number till it is less than n would be log(n). Let’s take the examples here. for n = 16, j = 2, 4, 8, 16 for n = 32, j = 2, 4, 8, 16, 32 So, j would run for O(log n) steps. i runs for n/2 steps. So, total steps = O(n/ 2 * log (n)) = O(n*logn) 4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y? Options:
Output: 2. X will always be a better choice for large inputsExplanation: In asymptotic analysis, we consider the growth of the algorithm in terms of input size. An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0. 5. What is the time complexity of the following code:
Options:
Output: Explanation: We have to find the smallest x such that ‘(N / 2^x )< 1 OR 2^x > N’ 6. Which of the following best describes the useful criterion for comparing the efficiency of algorithms?
Explanation: Comparing the efficiency of an algorithm depends on the time and memory taken by an algorithm. The algorithm which runs in lesser time and takes less memory even for a large input size is considered a more efficient algorithm. 7. How is time complexity measured?
8. What will be the time complexity of the following code?
Output: Explanation: Because loops for the kn-1 times, so after taking log it becomes logkn. 9. What will be the time complexity of the following code?
Output: 3. n(n-1)Explanation: First for loop will run for (n) times and another for loop will be run for (n-1) times so overall time will be n(n-1). 10. Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A. FalseExplanation: The Big-O notation provides an asymptotic comparison in the running time of algorithms. For n < n0, algorithm A might run faster than algorithm B, for instance. |