GATE CS 2022: Algorithm 2

Time complexity of an algorithm T(n), where n is the input size is given by

T(n) = T(n - 1) + 1/n, if n > 1

= 1, otherwise

The order of this algorithm is

The running time of an algorithm is represented by the following recurrence relation:

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

A certain problem is having an algorithm with the following recurrence relation:

T(1) = O(1)

How much time would the algorithm take to solve the problem?

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

Which of the following is correct?

Unsigned int f(unsigned int n, unsigned int r)

What is the Time Complexity of the above program?