0

“Formally, O-notation expresses the upper bound of a function within a constant factor. Specifically, if g(n) is an upper bound of f(n), then for some constant c it is possible to find a value of n, call it N, for which any value of n ≥ N will result in f(n) ≤ cg(n).”

This is a quote from a textbook I’m reading on algorithms. By this definition, O-notation would be meaningless?

If the running time of some algorithm is T(n) = 5n+10 then T(n) is O(n). But it is also O(n^2) and O(2^n), etc.

f(n) ≤ g(n)

5n+10 ≤ n^2 for n>6

5n+10 ≤ 2^n for n>5

I understand the concept of worst-case analysis. It just seems the notation has barely any link to algorithm complexity? It is very confusing.

programmist
  • 9
  • 1
  • Specifically what is meaningless about big O? It means exactly what the definition says. – Paul Hankin Jan 05 '21 at 14:14
  • I think you're saying that an upper bound is meaningless because you could choose a very bad upper bound. But a good (tight) upper bound is useful even if a bad upper bound is not useful. – Paul Hankin Jan 05 '21 at 14:17
  • What I see is meaningless is that we write some T1(n) is O(n) and some T2(n) is O(log n). Per the definition, it is just as correct to say T1 is O(n^3) and T2 is O(n^3). This would falsely imply the functions have equivalent complexity. – programmist Jan 05 '21 at 14:21
  • When you say "T(n) = O(n)", you are giving me information about T(n). This information is not meaningless. If you say "T(n) = O(n²)" instead, then you are giving me less information about T(n), because this second statement is a weaker statement. Just because it is possible to make a weaker statement doesn't mean that a statement is meaningless. The statement "It's -2°C today" is not meaningless; you could also have said "It's cold today" instead, or "Today doesn't look like a summer day", and both those statements would also have been true, but would have given less information. – Stef Jan 05 '21 at 14:39
  • 1
    @programmist If I say "3 < 10 and 5 < 10", would you conclude that 3 = 5 ? Surely not. Similarly, "T1(n) = O(n³) and T2(n) = O(n³)" does not imply that T1(n) = T2(n). – Stef Jan 05 '21 at 14:43

0 Answers0