Search code examples
algorithmtime-complexitybig-ocomplexity-theoryasymptotic-complexity

How to determine if a function is of a specific asymptotic type in algorithm analysis?

I'd like to have a better understanding of the asymptotic notation and how can one classify whether a function is of O notation of another function, and how can we tell whether f = o(g) || f != o(g)

For example:

enter image description here

For example, how can we tell that f = O(g)?

I've seen mostly this approach (solution below is unrelated to the question above):

enter image description here

But this is confusing as I don't undertand the way the prove this.

Please help me understand the core concept that is being applied here.

Thanks

Solution

  • We say that f is O(g) if we can find these two things:

    (1) We can find a constant "C" (You pick only one constnat , here i mean you can't change it later, this is most confusing part for beginners).

    (2) And a "N" (This is some lower bound, means for values greater than this N, our formula will be valid, once you reach end then come back and try to understand i mean by lower bound).

    such that whenever we plug in the value of n>= N then f(n) should be less or equal to C.g(n)

    Or in formula form:

    enter image description here

    Example:

    let's say i have a function f = 3n^2 + 4n + 3

    and one more function g = n^2

    Is f = O(g)?

    The leading term of f is 3n^2 , it means if i have a constant higher than 3 and i multiply it with g then f will be less than g.

    Let's take n = 4 > 3 then i get g = 4n^2 and my constant c is then 4.

    Now the question is what happends if i increase the value of n? If i plug in for example n = 4 then f(n) will not be less than g(n) but when i insert n = 5 then it is valid. so in this example c = 4 and N = 5.

    Now you have two different things in your question. This question below has nothing to do with Big-O notation , it's called tilde notation.

    Big-O throws constant terms away but tilde does not. It's more stricter form for the comparisons of algorithms. Here 22 means whenever n approaches infinity, the difference between f and g is approximately 22. However i prefer tilde notation but first you need to understand Big-O then you can go further.

    enter image description here

    For your this question : enter image description here

    You can see: both function have higher terms n namely f = 7n + ... and g = n. If i want to prove is f is o(g)

    Now if i ask for what value c c.g(n) is greater than f(n). Does there exist any constant c such that the formula is valid for all n >= some N.

    If i multiply g now with 7 (because f has leading constant 7) would this be valid? No because f has also factor of 8 with it, it means i need to increase constant c. Let's take it as 8 then still 7n + 8 > 8n if n = 1 but what happends when n >= 2 then g is always greater than f. So for constant c = 8 and n >= 2 f is o(g). You can also prove also that g is O(f). This is not difficult, you should get constant c = 1 and for n belonging to natural number