Answer each part TRUE or FALSE

a.n=o2n.b. 2n=on2.Ac.2n=o(3n).Ad.1=o(n).e.n=o(logn).f.1=o(1/n).

Short Answer

Expert verified

(a) n=0(2n)is true.

(b)2n=O(n2) true.

(c) 2n=O(3n)is true.

(d) 1=O(n)is true.

(e) n=o(log n)is false.

(f) 1=o(1n)is false.

Step by step solution

01

Step 1:To Calculate the correct theory

Here, it shows each part calculation which show correct theory and formula base answer in linear time,quadratic time etc.

02

To check whether equation is True or False

a) TRUE

2nseems to be linear time, therefore n represents linear time as well, thereforen=O(2n)

b) TRUE
n2Since has been quadratic whereas 2nseems to be linear,2n=O(n2)

c) TRUE
2n involves time that is exponentially andbecomes exponentially larger than 2nthus .2n=O(3n)

d) TRUE
1 represents continuous time (i.e., a moment), and therefore it is undeniably1=O(n) where n is linear times.

e) FALSE
nis linear timelogn Because it would be the logarithmic time, that's less than linear, ncouldbeinBigOoflogn.

f) FALSE
Important Note: 1=o(1n)s rather tough to obtain; it just implies that the algorithm will run quicker for a greater number of inputs; more tasks, less time; less tasks, more time.

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.

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

Say that two Boolean formulas are equivalentif they have the same set of variables and are true on the same set of assignments to those variables (i.e., they describe the same Boolean function). A Boolean formula is minimalif no shorter Boolean formula is equivalent to it. Let MIN-FORMULAbe the collection of minimal Boolean formulas. Show that if P = NP,MIN-FORMULA∈P

Let A⊆1* be any unary language. Show that if A is NP-complete, then P = NP. (Hint: Consider a polynomial time reduction f from SATto A. For a formula ϕ, let ϕ0100be the reduced formula where variables x1, x2, x3, and x4 inϕ are set to the values 0, 1, 0, and 0, respectively. What happens when you apply f to all of these exponentially many reduced formulas?)

Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string.

Let UNARY−SSUM be the subset sum problem in which all numbers are represented in unary. Why does the NP− completeness proof for SUBSET−SUM fail to show UNARY−SSUM is NP− complete? Show that UNARY−SSUM∈P

Show thatPRIMES={m|is a prime number in binary} ?. (Hint: Forp>1, the multiplicative groupZ*p={x|x is relatively prime toand } is both cyclic and of orderp-1ifpis prime. You may use this fact without justifying it. The stronger statementPis now known to be true, but it is more difficult to prove.)

See all solutions

Recommended explanations on Computer Science Textbooks

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