1
feynman
2y

Anyone got some good links to introduce Big-O notation? I’m getting my head around it but still feel I’m missing the basics!

Comments
  • 1
    It's all about calculus' limit operator.

    Basically, if you say that a function is O( somef(n) ) it means that its limit for n -> +inf is lower than somef(n) but it's also asymptotically equal to it.

    Formally, O( g(n) ) is a set of functions (let's call them f(n)) such that for each f(n) there exists at least one constant value c that makes
    0 <= f(n) <= c*g(n) true.
    (n is the length of your input, e.g. the length of an array)

    If your function is a O(g(n)) that means that is asymptotically lower or equal to g(n), while Ω(n) means the opposite. Θ(n) means BOTH.

    E.g. if my function is O(n^2) it means thay for big values of n it will take more or less n^2 time to execute.

    This comment isn't enough to understand this concept (and I wasn't very precise).
    Further readings: any algorithm book.
  • 1
    Thanks guys, I’ll crack it - just need to find some quite time to read it over and practice 👍🏼
    Thanks for the feedback!
  • 0
    May I introduce you to @bigOHNOtation
  • 0
    @Lor-inc feeling the username love right now
Add Comment