CrazyEngineers
CrazyEngineers

  • solve the recurrence problem with detail(time complexity)

    qwerty123

    qwerty123

    @qwerty123-ZuiVHD
    Updated: Oct 9, 2024
    Views: 1.3K
    solve the recurrence problem with detail(time complexity)

    T(n)=T(n-1)+1/n, if n>1
    = 1 otherwise
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • simplycoder

    Member • Apr 29, 2012

    To solve this,

    T(n)=T(n-1)+1/n
    put n=n-1
    T(n-1)=T(n-2)+1/(n-1)+1/n
    ...
    finally it will result in
    1/n+1/(n-1)+1/(n-2)+... +1/3+...

    For an infinite series, this can be approximated for ln
    Are you sure? This action cannot be undone.
    Cancel

  • nareshkumar6539

    Member • Apr 29, 2012

    T(n)=T(n-1)+1/n
    put n= n-1
    T(n)=T(n-2)+1/(n-1)+1/n
    and so on
    ............
    solve the total it will give sum of nth terms in harmonic series
    T(n)=1+1/2+1/3+.....+1/(n-3)+1/(n-2)+1/(n-1)+1/n
    approximately sum of n terms in harmonic series is ln(n)+.5772156649...
    T(n)=ln(n)+.5772156649
    timecomplextiy is O(ln(n))
    Are you sure? This action cannot be undone.
    Cancel

  • qwerty123

    Member • Apr 29, 2012

    hi, this problem uses log n series ....i can evalute only up to sum of n term ...........thanx for reply to this question........i already posted one question .......... average paged m/y access time question........till anyone cant solve the problem?....u solve the problem
    Are you sure? This action cannot be undone.
    Cancel

  • qwerty123

    Member • Apr 29, 2012

    Suppose the cache and main memory access times are 100 ns and 1200 ns respectively. The cache is used for paging and the hit ratio of finding the page table entry in the cache is 98%, what is the effective paged memory access time?

    (A) 240 ns (B) 220 ns(C) 250 ns (D) 1200 ns
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register