educative.io

Educative

Error in the introduction to complexity measures

ERROR
When c = 2 it is impossible for f(n) to be less than cn^3 ,you have mentioned this for n not greater than 4 which is again wrong as for any value f(n) which is 3n^3 will be greater than c*n^3 where c = 2.

Hi Akarsh!
The lesson has been updated. Thank you for your feedback!

Alina Fatima | Developer Advocate

1 Like

10^n is same as 2^n, but when i choose true, quiz says the answer is wrong.

Proof :

log(10^n) <= log(c2^n)

n log 10 < = logc + nlog2

log 10, log c, log 2 are all constant factors, rest that remains is n <=n which is true.

Hi Rohan,

10n is not in O(2n).

Let f(n) = 10n and g(n) = 2n.
Now,
f(n) = (10)n = (23.322)n
= (2n)3.322
= g(n)3.322

If f(n) = g(n)3.322 then,
f(n) can’t be in O(g(n)).

Hope this clarifies everything! Let me know if you have any other comments/questions/feedback.

Regards,
Alina Fatima | Developer Advocate

1 Like

Hi Alina,

Thanks for the details/clear/ with proof reply, really appreciate. This answers/clears by understanding.