Time Complexity

Question

Please help with the following in Time Complexity. 

1)Show that the following order-of-magnitude results hold:

a)3ⁿ=O(n!)

b)(n³ -2n)/(n+1)=theta(n²)

c)n³ /log(n+1)=O(n³) but not O(n²)

2)What is wrong with the following argument?

x=O(n⁴),y=O(n²),therefore x/y=O(n²).

3)

What is wrong with the following argument?

x=theta(n⁴),y=theta(n²),therefore x/y=theta(n²).

4)Assume that f(n)=2n² +n and g(n)=O(n²). What is wrong with the following argument?

f(n)=O(n²)+O(n), so that f(n)-g(n)=O(n² )+O(n)-O(n²). 

Therefore, f(n)-g(n)=O(n)

Comments

What is wrong with the following argument?

x=O(n⁴),y=O(n²),therefore x/y=O(n²).

let take y=n ( i didn't violate y=O(n²) ) and x=n⁴ =====> x/y = O(n³)

 

Assume that f(n)=2n² +n and g(n)=O(n²). What is wrong with the following argument?

f(n)=O(n²)+O(n), so that f(n)-g(n)=O(n² )+O(n)-O(n²). 

Therefore, f(n)-g(n)=O(n)

f(n) = O(n²) + O(n) = C₁. n².

g(n) = O(n²) = C₂ . n² .

f(n)-g(n) = (C₁ - C₂ ) . n² ===> (C₃) . n² ===> O(n²)

 

What is wrong with the following argument?

x=theta(n⁴),y=theta(n²),therefore x/y=theta(n²).

i didn't get, how it is wrong... according to me it is right.

---

a) 3ⁿ=O(n!)

             f(n)=O(g(n)) $\Rightarrow$  f(n) $\leq$ c*g(n)

             3ⁿ = 3*3*3*...*3  (n times)

              n! = 1*2*3*4....*n

          except fist and second value of n! all values are greater then corresponding values of 3ⁿ so 3ⁿ $\leq$ n!

b) (n³ -2n)/(n+1)=$\Theta$(n²)

         for asymptotic values of n : n $\cong$ n+1

         (n³ -2n)/n  = n²-2 = $\Theta$(n²)

c) n³ /log(n+1)=O(n³) but not O(n²)

      log(n+1) < n

      n³ / c*n = O(n²)

    when  n³ /log(n+1) then it will be $\Omega$(n²)

---

@ Dharmendra Lodhi

c) n³ /log(n+1)=O(n³) but not O(n²)

      log(n+1) < n

      n³ / c*n = O(n²)

    when  n³ /log(n+1) then it will be ΩΩ(n²)

i didn't get it.... is Option C is True or False ? ( according to you ) 

---

n³ /log(n+1) will be greater then n²  because if n³ /n=n² , and we know that n>log n so when small thing will divide then whole thing will be greater .