2

Is it common that a higher value for Big-O notation is used for convenience or simpler looks?

For example: I'm looking at this algorithm "bifragment gap carving" shortly explained here (page 66). If I understand it correctly the algorithm would take for any gap size n a maximum of sum from 1 to n but in the same document it says:

The technique does not scale for files fragmented with large gaps. If n is the number of clusters between bh and bz then in the worst case, n^2 object validations may be required before a successful recovery.

So my question is: Do I understand the algorithm wrong or was the worst-case runtime rounded up to n^2 to look nicer than a sum?

ap0
  • 1,083
  • 1
  • 12
  • 37
  • `O(n^2) = O(n*(n-1)/2)` – amit Aug 26 '14 at 07:28
  • 1
    Rounding is relevant for exact values, you're dealing here with an asymptotic bound so the term doesn't apply. – Leeor Aug 26 '14 at 07:30
  • Since the article doesn't mention big-O anywhere, I assume that `n^2` is the exact amount of object validations in the worst case. – Nico Schertler Aug 26 '14 at 07:33
  • Nico Schertler, you are right, sorry. But other articles I read for this algorithm actually used 'O(n^2)`. Thank you. – ap0 Aug 26 '14 at 07:36
  • The question (and answers) are focusing on how `O(n^2+n)=O(n^2)`. A more interesting question with the same title would be, for example, how common is `O(n^1.5 log n)` changed to `O(n^2)`. – Teepeemm Aug 26 '14 at 12:30
  • 1
    This question appears to be off-topic because it is about asymptotic analysis, not programming. – tmyklebu Aug 26 '14 at 17:15
  • Big-O notation is rounded to the **dominant term** – Khaled.K Aug 27 '14 at 09:41

3 Answers3

2

'sum from 1 to n' indeed equals (n + 1) * n / 2, or (n^2 / 2 + n / 2)

So, the order of magnitude is n^2 in this case. There is no simplification (you can obviously remove multiplicative constants like 1/2, and n << n^2 when n is large.

Orabîg
  • 11,718
  • 6
  • 38
  • 58
1

To answer the actual question: Yes, it's not just common but pretty much universal. O(N*N) means that the measure (usually runtime) goes up no faster than c * N *N for some unspecified c. Clearly N*N + N is smaller than 2 * N * N as N goes up, so O(N*N + N) is just O(N*N).

MSalters
  • 173,980
  • 10
  • 155
  • 350
1

The function f given in O(f) is an upper bound for the complexity of an algorithm. It means that for all inputs of size n (bigger than a certain size n0), your algorithm does not use more time (or space) than const*f(n).

That menas that if your algorithm does sum(i, i=0...n) steps ( which equals n*(n-1)/2 and is a quadratic function), const * n*n is a valid upper bound for all n>n0 --> and the complexity is O(n^2)

for another explanation look here: big o notation in plain english

Community
  • 1
  • 1
grishnagkh
  • 49
  • 4