solve the recurrence problem with detail(time complexity)
solve the recurrence problem with detail(time complexity)
T(n)=T(n-1)+1/n, if n>1
= 1 otherwise
T(n)=T(n-1)+1/n, if n>1
= 1 otherwise
Replies
-
simplycoderTo 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 -
nareshkumar6539T(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)) -
qwerty123hi, 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
-
qwerty123Suppose 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
You are reading an archived discussion.
Related Posts
Third world medicine need not be snake oil and charms. Sheer lack of resources forces innovators in the poorer countries to come up with biomedical solutions better than their counterparts...
I remember the days when people would refer to mobile phones as 'Nokia'. Nokia phones had made an impression in consumers minds as phones with superior build quality, almost unbreakable...
Gumroad is a new startup by three techies and led by a young Indian who earlier worked for Pinterest. Gumroad is all set to remove the pain from the whole...
i want mobile bug circuitry nd procedures can any one help me
I am an Mechanical Engineer...I want to do something extra in my fav. field(MECHANICAL)...thts y i m here...