Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

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.

Rating
• 蜉蝣
Lv 6

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): 國中數學老師的腦袋