Without using calculus (as in the previous exercise), show that, if n is a power of 2

Question:

Without using calculus (as in the previous exercise), show that, if n is a power of 2 greater than 1, then, for H_n, the nth harmonic number,

H_n ≤ 1 + H_n/2

Use this fact to conclude that Hn ≤ 1 + [log n], for any n ≥ 1.

Data From Previous Exercise

Use the fact that, for a decreasing integrable function, f,

cb+1 b f(x)dx < f (x)dx, r=a r=a-1 2=a

to show that, for the nth harmonic number, H_n,

ln n ≤ H_n ≤ 1 + ln n.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

See More Books

Question Posted: Aug 10, 2020 06:01 AM

See More Questions

Using the definition of a c-incremental algorithm from the previous exercise, show that, if a c-incremental algorithm A has a worst-case running time t(N) in the RAM model, as a function of the...
Consider the previous exercise, but suppose the city of Irvine, California, changed its dog-owning ordinance so that it still allows for residents to own a maximum of three dogs per household, but...
Solve the previous exercise using a queue instead of stack. That is, suppose you are given an array, A, containing n numbers in order, as in the previous exercise. Describe in pseudocode an efficient...
Suppose that in a wave of pessimism, housing prices fall by 10% across the entire economy. a. Has the stock of real assets of the economy changed? b. Are individuals less wealthy? c. Can you...
A fixed-end beam AB of length L supports a uniform load of intensity q (see figure). Beginning with the second-order differential equation of the deflection curve (the bending-moment equation),...
Consider two mutual funds for investment. Fund 1 is a bond fund with 5% average return and 10% standard deviation (STD) risk. Fund 2 is a stock fund with 10% average return and 15% STD risk. The...
A uniform magnetic field fills a cylindrical volume of radius $R$, and the field magnitude changes with time at an unknown rate. At a certain instant, the electric field magnitude at a radial...
The adjusted trial balance of College Book Store as of November 30, 2016, after the firms first month of operations, appears on the shown below. Appropriate adjustments have been made for the...
4. The atomic numbers of elements, U, V, W and X are 13, 14, 16 and 17 respectively. Which one of the elements will react with oxygen to form an ionic compound? (Atomic number of oxygen is 8) X A. B....
Using Thevenin's theorem, find o v in the circuit of Fig. 10.105. 3i 2 H 1200s , 12 cos V (
If one has a set, S, of n items, where n is even, then the median item in S is the average of the ith and (i + 1)st smallest elements in S, where i = n/2. Describe an efficient algorithm for...
What is H 5 , the 5th harmonic number?
James lives in a rent-controlled apartment and has for the past few weeks been trying to get the supervisor to fix his shower. Why does waiting to get ones shower fixed have to do with a...
What ethical considerations arise in the context of social change, particularly regarding issues of social justice, human rights, and intergenerational equity, and how do they inform strategies for...
Presley Plants manufactures custom planters for customers. During June, the company had the following account balances and transactions: Work in process inventory, June 1 $12,200 Work in process...
Reflect on the effective decision in Peter Drucker's on the Profession of ManagementLinks to an external site. and what you saw in the Five Functions of ManagementLinks to an external site. video....
What role do social movements, collective action, and grassroots mobilization play in instigating and sustaining processes of social change, and how do they interact with institutional structures and...
Choose a contemporary business trend (within the past 3 months) that has significantly impacted or has the potential to significantly impact the Canadian business landscape. This could be a trend...
Reggie contributed $10,000 in cash and a capital asset he had held for three years with a fair market value of $20,000 and tax basis of $10,000 for a 5 percent capital and profits interest in Green...
In your audit of Garza Company, you find that a physical inventory on December 31, 2012, showed merchandise with a cost of $441,000 was on hand at that date. You also discover the following items...
Give a complete justification of Proposition 12.1.
Show that the nodes of any AVL tree T can be colored red and black so that T becomes a red-black tree.
The boolean indicator used to mark nodes in a red-black tree as being red or black is not strictly needed when we have distinct keys. Describe a scheme for implementing a red-black tree without...
Find the integrating factor for the given 1-order linear non-homogeneous ordinary differential equation. Do not solve the ordinary differential equation. y xdx-xdy-x+dx + dx
[Bush] Consider the following snippet of code. (Assume that input strings, including null terminator, will always fit within the size 255 array.) char* to_upper_case(char* original) { char...
50. Show that if f(x) = a,x" + a-1x+...+x+ ao, a,..., a-1, and a,, are real numbers and where 0, then f(x) is O(x"). an # Big-O, big-Theta, and big-Omega notation can be extended to functions in more...

Without using calculus (as in the previous exercise), show that, if n is a power of 2

Question:

cb+1 b f(x)dx < f (x)dx, r=a r=a-1 2=a

Step by Step Answer:

If n is a power of 2 greater than 1 then there are n2 terms in the differe...View the full answer

Algorithm Design And Applications

Students also viewed these Computer science questions