- #1
enigmatic01
- 8
- 1
- Homework Statement
- Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b
- Relevant Equations
- ...
Homework Statement: Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b
Homework Equations: ...
This is how far I get:
let n = k+1
instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k - 30) therefore
= (10k⋅lgk + 32k - 30) + (10k⋅lgk + 32k - 30) + 10 + 10 + 30
I get stuck at this point
lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b
Homework Equations: ...
This is how far I get:
let n = k+1
instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k - 30) therefore
= (10k⋅lgk + 32k - 30) + (10k⋅lgk + 32k - 30) + 10 + 10 + 30
I get stuck at this point