Question

In: Computer Science

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))

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
1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the definition and proof of...
1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the definition and proof of big-O notation. 2- Prove using the definition of Omega notation that either 8 n is Ω (5 n ) or not. please help be with both
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
For each pair of functions f and g, write whether f is in O(g), Ω(g), or...
For each pair of functions f and g, write whether f is in O(g), Ω(g), or Θ(g). (latex format below)        \begin{enumerate}            \item $f = (n+1000)^4$, $g = n^4 - 3n^3$            \item $f = \log_{1000} n$, $g = \log_2 n$            \item $f = n^{1000}$, $g = n^2$            \item $f = 2^n$, $g = n!$            \item $f = n^n$, $g = n!$        \end{enumerate}
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.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT