Solution to 1. Find the theta notation of the following: a. 6n ³+ 12n ² + 1, … - Sikademy
Author Image

Archangel Macsika

1. Find the theta notation of the following: a. 6n ³+ 12n ² + 1, for nà ƒ ƒ ¢ ‰ ¥1 b. 3n ²+ 2n log2 n, for nà ƒ ƒ ¢ ‰ ¥1 2. Find the theta notation for the number of times the statement x:=x + 1 is executed. a. for i:=1 to 2n do x=x+1 b. for i;=1 to 2n do for i;=1 to n do X:=x +1

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

1.

Big-Theta(Θ) notation gives bound for a function f(n) to within a constant factor.

We write f(n) = Θ(g(n)), If there are positive constants n0 and c1 and csuch that, to the right of n0 the f(n) always lies between c1g(n) and c2g(n) inclusive.

Θ(g(n)) = {f(n) : There exist positive constant c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ cg(n), for all n ≥ n0


a.

c_1n^3\le 6n ³+ 12n ² + 1\le c_2n^3

f(n)=\theta(n^3)


b.

c_1n^2\le 3n ²+ 2n log2 n\le c_2n^2

f(n)=\theta(n^2)


2.

a.

f(n)=2n

c_1n\le 2n\le c_2n

f(n)=\theta(n)


b.

f(n)=2n^2

c_1n^2\le 2n^2\le c_2n^2

f(n)=\theta(n^2)


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1326-qpid-1064