If f(n) = 3n+2 and g(n) = n, then Prove that f(n) = O (g(n))

If f(n) = 3n+2 and g(n) = n, then Prove that f(n) = O (g(n))

Solutions

Expert Solution

Explanation :

Topic : Big O Notation

If f(n) <= c.g(n) for n>=0,

for some c>0 and n>1

Substitute f(n) = 3n+2

3n+2 <= c(b)

When can be 3n+2 less than equal to c(n),

For above case the value of c can be anything above 4 is better.

Eg. if we take c=4 and substitute in above equation then,

3n+2 <= 4n

2<= 4n -3n

2n<= n

It means for every n>= 2 at c=4, f(n)<=c.g(n).

f(n)= O (g(n))

Rakesh answered 1 year ago

Next > < Previous

Related Solutions

Prove why f(n)=big omega(g(n)) then f(n)=o(g(n)) is NEVER TRUE. Prove why f(n) +g(n) =Theta(max(f(n),g(n)) is ALWAYS...

Prove why f(n)=big omega(g(n)) then f(n)=o(g(n)) is NEVER TRUE. Prove why f(n) +g(n) =Theta(max(f(n),g(n)) is ALWAYS TRUE

Calculate the Big-O time complexity. Show work 1. n^2 + 3n + 2 2. (n^2 +...

Calculate the Big-O time complexity. Show work 1. n^2 + 3n + 2 2. (n^2 + n)(n ^2 + π/2 ) 3. 1 + 2 + 3 + · · · + n − 1 + n

Prove or disprove each of the followings. If f(n) = ω(g(n)), then log2(f(n)) = ω(log2g(n)), where...

Prove or disprove each of the followings. If f(n) = ω(g(n)), then log2(f(n)) = ω(log2g(n)), where f(n) and g(n) are positive functions. ω(n) + ω(n2) = theta(n). f(n)g(n) = ω(f(n)), where f(n) and g(n) are positive functions. If f(n) = theta(g(n)), then f(n) = theta(20 g(n)), where f(n) and g(n) are positive functions. If there are only finite number of points for which f(n) > g(n), then f(n) = O(g(n)), where f(n) and g(n) are positive functions.

if a in G (group ) such as o(a)=mn prove the existence of g and h...

if a in G (group ) such as o(a)=mn prove the existence of g and h in G such as a=gh=hg and o(g)=m o(h)=n

Prove and give a counterexample: If N ⊲ G and G ⊲ H, then N ⊲...

Prove and give a counterexample: If N ⊲ G and G ⊲ H, then N ⊲ H. Please write an explanation with some details

Derive the Sackur-Tetrode equation starting from the multiplicity givenin Ch. 2: Ω =(1/N!)(V^{N}/h^{3N})(pi^{3N/2}/3N^{2}!)(2mU)^{3N/2} The Sackur-Tetrode equation...

Derive the Sackur-Tetrode equation starting from the multiplicity givenin Ch. 2: Ω =(1/N!)(V^{N}/h^{3N})(pi^{3N/2}/3N^{2}!)(2mU)^{3N/2} The Sackur-Tetrode equation is: S=Nk[ln((V/N)((4pi*m*U)/(3Nh^{2}))^{3/2})+(5/2)]

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is...

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is 1-to-1 b) Prove: f is onto c) Prove {1, 2} x N is countable

Let F and G~be two vector fields in R2 . Prove that if F~ and G~...

Let F and G~be two vector fields in R2 . Prove that if F~ and G~ are both conservative, then F~ +G~ is also conservative. Note: Give a mathematical proof, not just an example.

6a. Show that 2/n = 1/3n + 5/3n and use this identity to obtain the unit...

6a. Show that 2/n = 1/3n + 5/3n and use this identity to obtain the unit fraction decompositions of 2/25 , 2/65 , and 2/85 as given in the 2/n table in the Rhind Mathematical Papyrus. 6b. Show that 2/mn = 1/ (m ((m+n)/ 2 )) + 1/ (n ((m+n)/ 2 )) and use this identity to obtain the unit fraction decompositions of 2/7 , 2/35 , and 2/91 as given in the 2/n table in the Rhind Mathematical Papyrus....

Prove (a) that ψ ± = N (x ± iy)f(r) is an eigenfunction of L^2 and...

Prove (a) that ψ ± = N (x ± iy)f(r) is an eigenfunction of L^2 and Lz and set the eigenvalues corresponding. (b) Construct a wave function ψ_0(r) that is an eigenfunction of L^2 whose eigenvalue is the same as that of a), but whose eigenvalue Lz differs by a unit of the one found in a). (c) Find an eigenfunction of L^2 and Lx, analogous to those of parts a) and b), which have the same eigenvalue L^2 but...

Subjects