Question

The recurrence relation T(n) = 7T(n/7) + n has the solution:
1. O(n)
2. O(logn)
3. O(nlog(n))
4. O(n²)

Answer 1

Correct Answer - Option 3 : O(nlog(n))

The correct answer is option 3.

Explanation:

Recurrence relation: T(n) = 7T(n/7) + n

Comparing with T(n) = aT(n/b) + θ(n^k log^pn)

a = 7, b = 7, k = 1, p = 0

Using Master's Theorem,

Since a = b^k and p > -1,

T(n) = O(nlog(n))