Complexity, Arrays and Strings

There exist constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0; it is an asymptotic upper bound.

Θ is a tight bound: f is bounded both above and below by constant multiples of g. O is only an upper bound, so 3n is O(n²) but not Θ(n²).

No. O, Θ, and Ω are bounds on a function; best, average, and worst case are separate choices of which function you bound. You can give an Ω bound on the worst case, for example.

For large n the highest-order term dominates, and constant factors depend on hardware and implementation rather than the algorithm's growth rate.

O(log n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

About 10⁸ simple operations per second is a common rule of thumb, so O(n log n) or O(n) is fine while O(n²) at 10¹⁰ operations is too slow.