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.

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.