Register

Doubt regarding Algorithms

• retagged by
757 views
0 votes
0 votes

Given $f(n)=n^2log n$ AND $g(n)=n(log n)^{10}$

Which one of the following is true?

  1. $f(n)=O(g(n))$
  2. $f(n)=\Omega(g(n))$
  3. $f(n)=\theta(g(n))$
  4. $\text{We can't compare.}$

Kindly work out this question. Stepwise solution. Thanx in advance. :)

• retagged by
User Avatar

1 Answer

0 votes
0 votes
f(n) = n (n log n)

g(n) = (n log n) $(log n)^{9}$   

cancelling n log n on both sides we have f(n)= n, and g(n) = $(log n)^{9}$  

n < (log n)9

example:  1. n = 1 , then f(n) = 1 and g(n) = 0.

                 2. n = 4 , then f(n) = 4 and g(n) = $2^{9}$

                 3. n = 128 / $2^{7}$, then f(n) = 128 and g(n) = $7^{9}$

                 4. n= 1024 / $2^{10}$ , then f(n) = 1024 and g(n) = $10^{9}$

Therefore f(n) < c g(n) where $n_{o}$ = 4. Hence f(n) = O(g(n)).

The answer is a.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
hem chandra joshi asked Oct 29, 2017
360 views
I have a basic question regarding DAA
let a function f(x) =$n^3$+$n^4$+1 so which are true 1. θ($n^4$) 2. θ($n^5$) 3. θ(1) 4. θ($n^3$) 5. Ω ($n^4$) 6. Ω ($n^5$) 7. Ω (1) 8. Ω ($n^3$) 9. O ($n^4$) 10. O ($n^5$) 11. O (1) 12. O ($n^3$) PLZ GIVE EXPLANATION WHICH ONE IS TRUE OR FALSE.
let a functionf(x) =$n^3$+$n^4$+1so which are true1. θ($n^4$)2. θ($n^5$)3. θ(1)4. θ($n^3$)5. Ω ($n^4$)6. Ω ($n^5$)7. Ω (1)8. Ω ($n^3$)9. O ($n^4$)10. O ($n^5$)11....
User Avatar
0 votes
0 votes
2 answers
2
Shashi Shekhar 1 asked Aug 1, 2018
349 views
Algorithms doubt
F(n)=n^(sin n) G(n)=n^(cos n) Why they are non comparable.
F(n)=n^(sin n)G(n)=n^(cos n)Why they are non comparable.
User Avatar
2 votes
2 votes
2 answers
3
aka 53 asked Nov 26, 2017
618 views
Doubt Algorithms Gate 2003
2^2n =O(2^n) True or False Its false but why
2^2n =O(2^n) True or FalseIts false but why
User Avatar
0 votes
0 votes
0 answers
4
aka 53 asked Nov 25, 2017
342 views
Doubt Algorithms
I wanted to know how θ is derived for a problem. Can we write it directly Example n^4 + n^3+ n^2 Here worst case will be n^4 since it is the term with highest power(worst). Similarly can i get θ
I wanted to know how θ is derived for a problem. Can we write it directly Example n^4 + n^3+ n^2 Here worst case will be n^4 since it is the term with highest power(wors...
User Avatar
Link Copied!