0
$\begingroup$

Edit: can someone provide clear answer with all details

Given:

$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$

I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)$

Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure)

But how I can prove that using recursion tree?

Here I did all of the calculations:

enter image description here

$\endgroup$
8
  • $\begingroup$ Please Note: the tree doesn't end here, I just wrote the first rows to understand $\endgroup$ – user128813 Nov 23 '20 at 12:33
  • $\begingroup$ You need to obtain both a lower-bound and an upper-bound for the number of operations. For the lower-bound, find 1) the depth of the shortest branch and 2) the number of operations for each level before that. Note that up to this depth all levels are full, so you can sum the number up to this level as per your picture. For the upper-bound, you find 1) the depth of the longest branch 2) an upper-bound on the number of operations for each level. Note that you can use $n (\frac 1{10} + \alpha)^k$ as an upper bound (the actual value is smaller since some branches halt earlier). $\endgroup$ – Dmitry Nov 23 '20 at 12:52
  • $\begingroup$ Why I care about upper bound? I only need the lower right? plus how may I know which one is smaller? $\endgroup$ – user128813 Nov 23 '20 at 12:55
  • $\begingroup$ "I was asked to find the minimum value for a for which T(n)=ω(n)". How do you know that the value is the smallest otherwise? By having a matching upper- and lower-bounds, you prove this. "plus how may I know which one is smaller?" Which what is smaller? $\endgroup$ – Dmitry Nov 23 '20 at 12:57
  • $\begingroup$ I refer to which depth is smaller, as u can see I found two depths. It will be cool if you can submit an answer with some more details since still I'm not convinced I need higher bound $\endgroup$ – user128813 Nov 23 '20 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.