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

There are many variants of Rudrata’s problem, depending on whether the graph is undirected or directed, and whether a cycle or path is sought. Reduce the DIRECTED RUDRATA PATH problem to each of the following.(a)The (undirected) RUDRATA PATH problem.(b) The undirected RUDRATA PATH problem, which is just like RUDRATA PATH except that the endpoints of the path are specified in the input.

Show that any array of integers x[1…n] can be sorted in O (n + M) time, where

role="math" localid="1659938331794" M=maxxi-minxiii

For small M, this is linear time: why doesn’t the Ω(nlogn) lower bound apply in this case?

Mean and median. One of the most basic tasks in statistics is to summarize a set of observations x1,x2,…,xn⊆R by a single number. Two popular choices for this summary statistic are:

• The median, which we’ll callμ1

• The mean, which we’ll callμ2

(a) Show that the median is the value of μthat minimizes the function

∑i|xi-μ|

You can assume for simplicity that is odd. (Hint: Show that for any , the function decreases if you move either slightly to the left or slightly to the right.)

(b) Show that the mean is the value of μ that minimizes the function

∑i(xi-μ)2

One way to do this is by calculus. Another method is to prove that for any μ∈R,

∑i(xi-μ)2=∑i(xi-μ2)2+n(μ-μ2)2

Notice how the function for μ2 penalizes points that are far from much more heavily than the function for μ1 . Thus μ2 tries much harder to be close to all the observations. This might sound like a good thing at some level, but it is statistically undesirable because just a few outliers can severely throw off the estimate of μ2 . It is therefore sometimes said that μ1 is a more robust estimator than μ2 . Worse than either of them, however, is μ∞ , the value of μthat minimizes the function

maxi|xi-μ|

(c) Show that μ∞ can be computed in O(n) time (assuming the numbers are xismall enough that basic arithmetic operations on them take unit time).

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

|ψ›=12|00›+12|11›is one of the famous “Bell states,” a highly entangled state of its two qubits. In this question we examine some of its strange properties. (a) Suppose this Bell state could be decomposed as the (tensor) product of two qubits (recall the box on page ), the first in state α0|0›+α1|1and the second in stateβ0|0›+β1|1. Write four equations that the amplitudes α0,α1,β0andβ1must satisfy. Conclude that the Bell state cannot be so decomposed.

(b) What is the result of measuring the first qubit of |ψ⟩?

(c) What is the result of measuring the second qubit after measuring the first qubit? (d) If the two qubits in state|ψ⟩ are very far from each other, can you see why the answer to (c) is surprising?
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Programming

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Systems

Read Explanation

Game Design in Computer Science

Read Explanation

Data Representation 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