List the Big-Oh notation that corresponds to each of the following examples. (5

Question

List the Big-Oh notation that corresponds to each of the following examples. (5 pts. each) (1.1) A bacteria that doubles itself every generation. (1.2) After crafting a Huffman tree, finding out the binary code that represents a given character. (1.3) Pulling a single ball out of a pit filled with them. (1.4) Hammering a stake into every square of a lawn cut to resemble a chessboard. (1.5) Shaking hands with everyone in a room. (1.6) Repeatedly cloning yourself to cut down the time it takes you to clean your entire house.

Explanation / Answer

doubles every generation

so x_(n+1) = x_(n) *2

and hence x_n = O(2^n)

1.2) please explain this part in the comments

1.3) pulling a single ball will take a constant time. O(1)

1.4) O(n^2) squares in a lawn

1.5) shaking hands with everyone in a room with n members . O(n)

if every one in the room shakes hands with every other O(n^2)

1.6) repeatedly cloning gives O(2^n) you

and the time reduced to O(logn)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.