Introduction to Big O
Big O Notation Big O is defined as the asymptotic upper limit of a function. In plain english, it means that is a function that cover the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms. Growth Rate Name 1 Constant log(n) Logarithmic n Linear n log(n) Linearithmic n^2 Quadratic n^3 Cubic 2^n Exponential This is kinda abstract let’s see what it means in code: Growth Rate Name Code Example description 1 Constant a= b + 1; statement (one line of code) log(n) Logarithmic while(n>1){ n=n/2; } Divide in half (binary search) n Linear for(c=0; c<n; c++){ a+=1; } Loop n*log(n) Linearithmic Mergesort, Quicksort, … Effective sorting algorithms n^2 Quadratic for(c=0; c<n; c++){ for(i=0; i<n; i++){ a+=1; } } Double loop n^3 Cubic for(c=0; c<n; c++){ for(i=0; i<n; i++){ for(x=0; x<n; x++){ a+=1; } } } Triple loop