edited by
3,009 views
3 votes
3 votes

Give as good a big-O estimate as possible for the following functions:

$(n \log n+ n^2 )(n^3 +2) \text{ and } (n! +2^n) (n^3 + \log (n^2 +1))$

  1. $O(n^5 + 2n^2) \text{ & } O(n^{3*}n!)$
  2. $O(n^5) \text{ & } O(n^{3*}2^n)$
  3. $O(n^5) \text{ & } O(n^{3*}n!)$
  4. $O(n^5 + 2n^2) \text{& } O(n^{3*}2^n)$
edited by

2 Answers

3 votes
3 votes

Ans is C  in first function n^5 will dominate rest term as n approaches large  and in second function n^3 x n! will dominate rest terms as n become large  

O(n5) & O(n3n!) O(n5) & O(n3∗n!)

2 votes
2 votes

Answer B)

(n log n + n2)(n3+2)

=n4 log n + n5 + 2 n log n + 2 n2

for Big O $0\leq f(n)\leq cg(n)$

Here n4 log n + n5 + 2 n log n + 2 n2 $\leq$ 2n5

then n4 log n + n5 + 2 n log n + 2 n2 =O(n5)

Similarly,

(n!+2n)(n3+log(n2+1))=n!n3+n!log(n2+1)+2nn3+2nlog(n2+1)

                             =O(n!n3)

Say, if we take log in n! and 2n , we get n! growth rate >> 2n

edited by
Answer:

Related questions

1 votes
1 votes
1 answer
1
go_editor asked Jul 14, 2016
2,758 views
In classful addressing, the IP address 190.255.254.254 belongs toClass AClass BClass CClass D
3 votes
3 votes
1 answer
2
Shimpy Goyal asked Jun 25, 2015
10,901 views
Using data p=3, q=11, n=pq, d=7 in RSA algorithm find the cipher text of the given plain text SUZANNEBUTAEEZSUZANNEXYZABCDABCDXYZ
1 votes
1 votes
1 answer
3
go_editor asked Jul 14, 2016
2,179 views
The $mv$ command changesthe inodethe inode-numberthe directory entryboth the directory entry and the inode