Question

There are two matrices A and B of size nXn. The data in both these matrices
resides only at positions where both the indices are a perfect square. Rest all
positions have 0 as the data. Manuj has available a third matrix initialized with 0's at
all positions. He writes an efficient code to put the sum of A and B in C. What is the
time complexity of Manuj's program?
Op 1: θ(n^2)
Op 2: θ(n)
Op 3: θ(n1/2)
Op 4: θ(log(n))

Answer 1

Answer:

$\large{\bf{\blue{\underline{\underline{Hii...!!}}}}}$

Option 2

Hope it helps

Answer 2

Answer:

The correct answer is Option 2

Explanation:

• O(N²) represents the complexity of an algorithm, whose performance is proportional to the square of the size of the input elements. It is generally quite slow: If the input array has 1 element it will do 1 operation, if it has 10 elements it will do 100 operations, and so on.
• O(logN) describes an algorithm that its number of operations increases by one each time the data is doubled.
• Linear running time algorithms are widespread. These algorithms imply that the program visits every element from the input.
• Linear time complexity O(n) means that the algorithms take proportionally longer to complete as the input grows.
• sqrt(n) is the number that minimizes function max(k, n/k) which turns out to be useful in a few algorithms problems.