wcwcwc asked in 科學數學 · 1 decade ago

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

Rating
  • 蜉蝣
    Lv 6
    1 decade ago
    Favorite 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): 國中數學老師的腦袋
Still have questions? Get your answers by asking now.