'What will be complexity of reccurance relation : T (n) = 0.5T (n/2) + 1/n
How to calculate the complexity of this case since master method fails for a<1?
Solution 1:[1]
Let's solve the recurrence relation below:
T(n) = (1/2) * T(n/2) + (1/n)
T(n/2) = (1/2) * T(n/4) + (1/(2/n))
Therefore:
T(n) = (1/4) * T(n/4) + (1/n) + (1/n) Notice the pattern.
In overall:
T(n) = (1/2^k) * T(n/2^k) + (1/n)*k
2^k = n --> k = log(n)
T(n) = (1/n) * T(1) + (1/n)*log(n)
T(n) = (log(n) + c)/n c = constant
T(n) ~ log(n)/n
Notice that as n goes to infinity, total number of operations goes to zero.
Recall the formal definition of Big-Oh notation:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ? f(n) ? cg(n) for all n ? k.
T(n) = O(1) since 0 <= T(n) <= c*1 for all n >= k for some k>0 and c>0.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Muhteva |