Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q2E (page 18)

Show that, if c is a positive real number, then g(n) = 1 + c + c2 + · · · + cn is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

(c) Θ(cn) if c > 1.

The moral: in big-Θ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

Short Answer

Expert verified

The sum of the series can be calculated by using the following formula:

sn=a(rn-1)r-1

Where a is the first term of the GP and r is the common ratio.

Step by step solution

01

Simplifying the Geometric Progression

For the given series,

a=1,r=c

Applying the sum of the GP formula, we get:

sn=1cn-1c-1=cn-1c-1

02

Proving the result for c < 1 using the hit and trial method.

let ,c =0 which is less than 1, and put the value of c in sn, we get:

sn=0n-10-1=0-1-1∵on=0=1

Therefore, we can say thatg(n) is Θ(1)whenc<1.

03

for c = 1,

Use the limits to prove this,

limc→1cn-1c-1=n.1n-1∵limx→axn-anx-anan-1=n.1=n

So,

sn=n⊙sn=⊙n

04

for c > 1

For any number c > 1, the last term of the series can be used to find the theta notation of the entire series because that term will be largest. So, the last term of the series is cnwhose theta notation will beΘ(cn)

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

How long does the recursive multiplication algorithm (page 25) take to multiply an n -bit number by an m -bit number? Justify your answer.

The Fibonacci numbers F0,F1,F2,... are defined by the rule

F0=0,F1=1,Fn=Fn−1+Fn−2.

In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.

(a) Use induction to prove that Fn≥20.5nfor n≥6.

(b) Find a constant c<1such thatFn≥2cn for all n≥0. Show that your answer is correct.

(c) What is the largestc you can find for which Fn=Ω(2cn)?

Is there a faster way to compute the nth Fibonacci number than by fib2 (page 4)? One idea involves matrices.

We start by writing the equations F1=F1 and F2=F0+F1 in matrix notation:


role="math" localid="1659767046297" (F1F2)=(0111).(F0F1).

Similarly,

F2F3=(0111).(F1F2)=(0111)2.(F0F1)

And in general

(FnFn+1)=(0111)n.(F0F1)

So, in order to compute Fn, it suffices to raise this 2×2 matrix, call it X, to the nth power.

a. Show that two 2×2matrices can be multiplied using 4additions and 8multiplications.

But how many matrix multiplications does it take to compute Xn?

b. Show that O(logn) matrix multiplications suffice for computing Xn. (Hint: Think about computing X8.)

Thus, the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is just O(logn), as compared to O(n)for fib2. Have we broken another exponential barrier? The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time offib2becomes O(n).

c. Show that all intermediate results of fib3 are O(n) bits long.


d. Let M(n)be the running time of an algorithm for multiplying n-bit numbers, and assume that M(n)=O(n2) (the school method for multiplication, recalled in Chapter 1, achieves this). Prove that the running time of fib3 is O(M(n)logn).


e. Can you prove that the running time of fib3 is O(M(n))? Assume M(n)=Θ(na)for some 1≤a≤2. (Hint: The lengths of the numbers being multiplied get doubled with every squaring.)


In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit integers faster thanO(n2) . Do you think this is possible? (The answer is in Chapter 2.) Finally, there is a formula for the Fibonacci numbers:

role="math" localid="1659768125292" Fn=15(1+52)n−15(1−52)n.

So, it would appear that we only need to raise a couple of numbers to the nth power in order to computeFn . The problem is that these numbers are irrational, and computing them to sufficient accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of raising these irrational numbers to the nth power. If you know your linear algebra, you should see why. (Hint: What are the eigenvalues of the matrix X?)

Question: An Eulerian tourin an undirected graph is a cycle that is allowed to pass through each vertex multiple times, but must use each edge exactly once.

This simple concept was used by Euler in to solve the famous Konigsberg bridge problem, which launched the field of graph theory. The city of Konigsberg (now called Kaliningrad, in western Russia) is the meeting point of two rivers with a small island in the middle. There are seven bridges across the rivers, and a popular recreational question of the time was to determine whether it is possible to perform a tour in which each bridge is crossed exactly once. Euler formulated the relevant information as a graph with four nodes (denoting land masses) and seven edges (denoting bridges), as shown here.

Notice an unusual feature of this problem: multiple edges between certain pairs of nodes.

(a) Show that an undirected graph has an Eulerian tour if and only if all its vertices have even degree. Conclude that there is no Eulerian tour of the Konigsberg bridges.

(b) An Eulerian pathis a path which uses each edge exactly once. Can you give a similar if-and-only-if characterization of which undirected graphs have Eulerian paths?

(c) Can you give an analog of part (a) for directedgraphs?

Question: 0.1. In each of the following situations, indicate whether f=O(g),orf=Ω(g),or both (in which case f=⊙(g))
See all solutions

Recommended explanations on Computer Science Textbooks

Databases

Read Explanation

Functional Programming

Read Explanation

Computer Organisation and Architecture

Read Explanation

Problem Solving Techniques

Read Explanation

Issues in Computer Science

Read Explanation

Big Data

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free