# Computational complexity

in each of the following, f as an positive integer. solve for f(n) relative to the given set S, and determine the appropriate "O" form for f on s 1). f(1)=0 f(n)=2f(n/5)+3, n= 5,25,125,,, S={5^i : i as an element of natural number} 2).f(1)=1 f(n)=f(n/2)+2, n=2,4,8,,, S={2^i : i as an element... 顯示更多 in each of the following, f as an positive integer.
solve for f(n) relative to the given set S, and determine the appropriate "O" form for f on s

1). f(1)=0
f(n)=2f(n/5)+3, n= 5,25,125,,,
S={5^i : i as an element of natural number}

2).f(1)=1
f(n)=f(n/2)+2, n=2,4,8,,,
S={2^i : i as an element of natural number}

*"O" means dominate.
1 個解答 1