Thread: Recurrance

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    113

    Recurrance

    I am stuck on this question from cormen(unsolved of course) and need your help

    p(n)={1 ifn=1
    {summation of k=1 to n-1 P(k)P(n-k) ifn>=2

    Prove that solution of this recurrance is omega(2^n) by substitution.

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    I think your problem is that it's not.

    Experimentally...

    i, p(i), p(i)/p(i-1)

    Code:
    >>> for i in range(2, 40): print i, p(i), float(p(i)) / p(i - 1)
    ... 
    2 1 1.0
    3 2 2.0
    4 5 2.5
    5 14 2.8
    6 42 3.0
    7 132 3.14285714286
    8 429 3.25
    9 1430 3.33333333333
    10 4862 3.4
    11 16796 3.45454545455
    12 58786 3.5
    13 208012 3.53846153846
    14 742900 3.57142857143
    15 2674440 3.6
    16 9694845 3.625
    17 35357670 3.64705882353
    18 129644790 3.66666666667
    19 477638700 3.68421052632
    20 1767263190 3.7
    21 6564120420 3.71428571429
    22 24466267020 3.72727272727
    23 91482563640 3.73913043478
    24 343059613650 3.75
    25 1289904147324 3.76
    26 4861946401452 3.76923076923
    27 18367353072152 3.77777777778
    28 69533550916004 3.78571428571
    29 263747951750360 3.79310344828
    30 1002242216651368 3.8
    31 3814986502092304 3.8064516129
    32 14544636039226909 3.8125
    33 55534064877048198 3.81818181818
    34 212336130412243110 3.82352941176
    35 812944042149730764 3.82857142857
    36 3116285494907301262 3.83333333333
    37 11959798385860453492 3.83783783784
    38 45950804324621742364 3.84210526316
    39 176733862787006701400 3.84615384615
    Looks like omega(4^n) to me.

    Code:
    >>> print float(p(500))/ p(499)
    
    3.988
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed