Mitchell Faas
Mitchell Faas

Reputation: 440

how to evaluate equality of big O notation?

I've been asked a question that seems strange to me. Given the following two equalities, which is true, and which is false (or are they both either true or false)?

  1. O(n^2) = O(n^3)

  2. O(n^3) = O(n^2)

To me, this question seems absurd, since O(f(n)) just means that for some time function T(n), lim as n -> infty of T(n) <= c * f(n).

Upvotes: 0

Views: 289

Answers (1)

PF. Castro
PF. Castro

Reputation: 144

O(f(n)) can be thought of as the class of all functions whose growth is bounded above by f(n). Taking into account this, the two options are false.

Upvotes: 1

Related Questions