10 ms·
<It’s not straightforward to prove why this is O(n). Replace T(n/5) with T(floor(n/5)) and T(7n/10) with T(floor(7n/10)) and show by induction that T(n) <= 10n
by beyondCritics 2y ago
<It’s not straightforward to prove why this is O(n).
Replace T(n/5) with T(floor(n/5)) and T(7n/10) with T(floor(7n/10)) and show by induction that T(n) <= 10n for all n.