Algorithm Analysis and Complexity

What is the time complexity of a binary search algorithm?

• O(log n)

• O(n log n)

• O(1)

• O(n)

Explain the difference between time complexity and space complexity.

• Time complexity and space complexity are interchangeable terms used in algorithm analysis.

• Time complexity focuses on execution time, whereas space complexity focuses on memory usage.

• Time complexity is only concerned with the worst-case scenario, whereas space complexity is always constant.

• Time complexity measures the number of operations, while space complexity measures the speed of the algorithm.

Below is not the Application of Divide and Conquer Algorithm

• Binary search

• merge sort

• quicksort

• linear search

Below is not the property of an algorithm

• findness

• input

• effectiveness

• finiteness

Omega formulae

• f(n)>=c(g(n))

• f(n)<=c(g(n))

• c1.(g(n))<=f(n)<=c2.(g(n))

• none

Which of the following is not an asymptotic notation

• O

• Ω

• None

• ω

main()

{

c=a+b;

}

This code time complexity

• O(n)

• O(2)

• O(1)

• O(0)

Explain how recursion affects the time complexity of an algorithm.

• Recursion only affects space complexity, not time complexity.

• Recursion has no impact on time complexity.

• Recursion always reduces time complexity in algorithms.

• Recursion can increase time complexity, often leading to exponential growth in cases like naive Fibonacci calculations.

If an algorithm takes the minimum amount of time for its execution, then it is called

• best case

• worst case

• none

• average case

How can you analyze the time complexity of a nested loop?

• O(n) where n is the total number of iterations in both loops combined.

• O(n * m) where n is the outer loop iterations and m is the inner loop iterations.

• O(n + m) where n is the outer loop iterations and m is the inner loop iterations.

• O(m) where m is the number of iterations in the inner loop only.