CODEWITHSUNDEEP
big-o
shiteatlife
shiteatlife

Reputation: 67

O=(N²) slower when executed ten times?

I have two for loops which means I have O=(N²). So if N is 5000 it would be, 25000000(if it's executed once). If I execute it once this is correct but if I execute it 10 times, it takes much more steps. Is this supposed to happen?

Upvotes: 0

Views: 38

Answers (1)

clemens
clemens

Reputation: 17712

The big-O notation is for describing the asymptotic number of steps of algorithms. It is for comparing different algorithm for large inputs. For instance heap sort and merge sort are in O(n log n). Thus, they are asymptotically faster than insertion sort which is in O(n^2).

Running the same algorithm a constant number doesn't change its complexity, and the big-O class is just an estimation and not an exact measure for the number of steps. Thus, saying your algorithm needs 25,000,000 steps must not be correct (e. g. n(n - 1) / 1,000,000 is in O(n^2), too).

Upvotes: 1

Related Questions