3 ms·

Can anyone recommend an alternative introduction to asymptotic notation?

• contravariant 10y ago
  Different in what way? The general idea is that something takes O(f(n)) time if it takes at most C·f(n) time for some constant C and all but finitely many values of n. The 'all but finitely many values' is what makes this definition 'asymptotic'. Basically 'O(f(n))' ignores constant factors and the behaviour at 'small' n (i.e. small inputs), the reasoning behind this is that an algorithm in O(f(n)) is faster than any algorithm not in O(f(n)) provided you make the input big enough. The little o, big Omega, big Theta are just small variations on this, which won't be too hard to understand if you get the general concept, and really the distinction isn't too important usually, just know that O(f(n)) gives an upper bound, not necessarily the best possible upper bound. To understand the big-O notation better it might help to have some basic knowledge of limits.
  • evahop 10y ago
    The information made intuitive sense to me. I just couldn't apply what was read directly to the exercises. It felt as though something crucial had been omitted. That something turns out to be calculus.
    • contravariant 10y ago
      You don't technically need calculus, but knowing about limits does help.
      • evahop 10y ago
        I appreciate the insight. For w/e reason this has been one of the more difficult concepts to grasp.