CODEWITHSUNDEEP
complexity-theorybig-o
Navid Koochooloo
Navid Koochooloo

Reputation: 277

complexity -big O notation , theta and omega

can anyone help me verifying the following complexities:

    10^12 = O(1)?
    2^(n+3) + log(n) = O(2^n)?
    f(n) = Omega(n) and f(n) = theta(n) <=> f(n) = O(n)

thanks

Upvotes: 1

Views: 835

Answers (1)

user2471961
user2471961

Reputation:

The first two are right, the last is wrong.

In particular, any value that has no variable attached will be "a constant" and therefore O(1). As for why you're correct on the second, 2^n strictly beats log(n) asymptotically, and 2^(n+3) is equivalent to 8*2^n, or O(1)*O(2^n), and it's generally best to simplify big-O notation to the simplest-looking correct form.

The third condition is wrong because f(n) = O(n) does not imply either of the first two statements.

Upvotes: 1

Related Questions