Asymptotic Notation

Asymptotic Notation, or Landau Notation

Asymptotic Notation is used to describe the limiting behavior of a function as it approaches a particular value or infinity.

We have already seen a glimpse of this in the last post when we were discussing Order of Growth of functions.  Ex: O(n)

When discussing asymptotic notation, there are three key terms:

  1. Theta Notation - A function that bounds a function within constant factor after a particular n.
  2. Big O Notation - represents the upper bound of Theta-Notation.
  3. Big Omega Notation - represents the lower bound of theta-notation.
Taken from: Florida State University

In the graph above, (c2 g(n)) represents Big O Notation, because for each n after n0, O(g(n)) >= f(n).  
(c1 g(n)) represents Big Omega Notation because for each n after n0, Omega(g(n)) <=  f(n).
There is an O-notation and Omega-notation, so therefore there exists a Theta-notation for the function f(n).

  1. For O-notation and Omega-notation are both the same function g(n), but differ by some constants c1 and c2.
  2. When discussing the run-time of algorithms in terms of asymptotic notation, we must make sure what exactly we are specifying.  Take for example saying that insertion sort that O(n^2) means that insertion sort runs at n^2 for all input, but rather it will run no slower than O(n^2).  We know that insertion sort does not always run at O(n^2) because we know that in the best-case where the input is already sorted, it will run in Theta(n).
Asymptotically tight - means that the asymptotic notation of a bound is the same factor of n as f(n).  

For Example: 
n^2  = O(n^2)    Is tight
2n = O(n^2)       Is not tight.  2n = o(n^2)

Little-oh Notation - when 0-notation is not asymptotically tight.  o(n).
That means for some constant c, O(cg(n)) >= f(n).  A not asymptotically tight function would be for all constant c, O(cg(n)) > f(n).

w-notation, or little omega notation, is the similar to little-oh notation, but for omega notation.

Comments

Post a Comment

Popular posts from this blog

Uncle Bob's Clean Architecture

Image
The basis of my current understanding of architecture comes from the brilliant mind of Robert C. Martin (Uncle Bob). You can find the original post through his blog , which I strongly encourage you to read. In this post I'll try to summarize some of the key points I've understood from his post. Clean Architecture Source Clean architecture is a design used to emphasize the structure and relation of your various code components to promote the idea of Dependency Rule , such that "source code dependencies only point inwards" . Clean architecture is able to promote this by defining that your software system consists of various layers , that can be organized in such a way that the layers point in one direction, and a dependency graph will not have circular reference. The reason this is important is because it allows you to keep closely code related, and increase clarity of how components fit into your system. Explaining the Layers We can really separate out this ...
Read more

C4 Model: Describing Software Architecture

Image
The point behind a presentation of Visualizing Software Architecture , by Simon Brown, was that we need to standardize the way software developers communicate with each other in respect to our discussions of software architecture. As part of Simon's consultation, one exercise he gave to software architects was a simple task to white board the architecture of a software system. The results he received varied immensely, and there was never a defacto standard format that he received from this exercise. When inspecting the feedback from the participants, the general answer was that it was easy to come up with the design, but difficult to properly put their ideas onto paper, or white board in this case. White Board Example, c4model.com Simon sought to start a movement by defining a set of organizational rules to help us describe our software architecture with a set of standard terminologies. His work has let to C4 Model , which stands for C ontext, C ontainers, C omponents,...
Read more

Running RabbitMQ with Docker

Image
Short post today, mostly just wanted to how to setup RabbitMQ for local development. Refer back to my previous post to learn more about RabbitMQ. Prerequisite Docker For complete guide reference, check out the Docker Hub Website for RabbitMQ . Why use Docker? Before starting my current job at iHerb, I would go straight for the Windows installation (my development environment) for all of my development tools needs. It was straight forward and "just worked" a lot of the time. What I've begun to realize experimenting with all these different tooling and services is that things can get a bit cluttered, you will have a bunch of supporting systems that need to be run - caches, queues, databases and it can be a hassle to manage them through window services and executables. Additionally some of these require additional dependencies outside of the executable itself, which prompts you to install even more tooling. The great thing about docker is that it defi...
Read more