# 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 of natural number}

*"O" means dominate.

### 1 Answer

- 蜉蝣Lv 61 decade agoFavorite Answer
1). f(1)=0

f(n)=2f(n/5)+3, n= 5,25,125,,,

S={5^i : i as an element of natural number}

---

f(5)=2f(1)+3=3=3*(1)

f(5^2)=2f(5)+3=2*3+3=3(2^1+1)

f(5^3)=2(2*3+3)+3=2^2*3+2*3+3=3*(2^2+2^1+1)

.........

f(5^i)=3*(2^(i-1)+2^(i-2)+......+2+1)=3*(2^i-1)---[1+2+...公比為2之等比級數]

(i=1,2....)

-------------------------------------------

2).f(1)=1

f(n)=f(n/2)+2, n=2,4,8,,,

S={2^i : i as an element of natural number}

f(2)=f(1)+2=1+2

f(2^2)=f(2)+2=1+2+2

f(2^3)=f(4)+2=1+2+2+2

.........

f(2^i)=1+2+2+...+2(共i個2)=2i+1

(i=1,2....)

若有不懂之處歡迎提出

Source(s): 國中數學老師的腦袋