Menu
So I am pretty sure it is O(n) (but it might not be?), but how do you solve it with substitution?
If you assume T(n) <= c * n, what is the induction steps?
932
Substitution Method:We make a guess for the solution and then we use mathematical induction to prove the guess is correct or incorrect. We guess the solution as T(n) = O(nLogn). Now we use induction to prove our guess. We need to prove that T(n) <= cnLogn.
Hence answer is O(N).
Time Complexity =O(1).
Hence the complexity of above Algorithm is O(logn).
First of all,I'd like to assume clearly that Θ(1)=k,some constant.
Next,proceeding using substitution method, we get
T(n)=2T(n/2)+Θ(1)
=2T(n/2)+k
=2{2T(n/4)+k)+k
=4T(n/4)+3k
=...
=n.T(1)+(n-1)k
=n.k+(n-1)k
=2nk-k
=O(n).
If you assume it as T(n) <= c * n,you should start with T(1) and assume for T(n) to be correct,and then proceed to show that it is correct for T(n+1) by using the assumption for T(n).
BTW,your assumption was right!
152
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
