true / false

Question

i geeting ans 1 and 2 are true but ans given only 2 is true explain it

Comments

n+1!=n+1(n!) so n!=O(n+1!)

Answer 1

see the difference . The 3! and 4! differ by 21. as the value get large they differ by a large amount . ex 11! and 10!. so we can't say 1 well we can't say 4 also as logn> less than loglogn. in option 2. log n base 4 = logn base2 *1/2 so complexity will be same.

Answer 2

(n+1)!  = (n+1)* (n)*(n-1)*........1  =  (n+1)*(n!)   > n!

Hence   n! =  O((n+1)!) => option (1) is wrong.

log₄n  = (1/2)* log₂n, So we can write log₂n as follows:

(1/2)* log₂n  ≤ (1/2)* log₂n ≤ log₂n   => (1/2)* log₂n  = ⊝(log₂n)  => log₄n = ⊝(log₂n)  Hence (!!) is correct.

√logn ≥ loglogn => loglogn  = O(√logn)   => (!!!) is wrong.

Hence only (!!) is correct. Hence option (C) is correct.