Algorithms Terminalogy

Introduction:

Software engineers want to solve problems and as software as evolved so has algorithms. Many problems have been solved by implementing algorithms. There are many performance benefits by implementing algorithms. Today I will explain some concepts one should familiarize themselves with when deciding to study Data Structures and Algorithms.

What does this function do:

function p(){

console.log("c")

}

It takes one step to operate. As you can see there is no for loop. When we analyze this we say this is in constant time.

Linear runtime

Linear runtime is the amount of operations happening for each line executed by a for loop.

Ex.

void printAll (char** c, int v){

     for(i=0;i<v;i++){

          cout << c[i] <<endl;

     }

}

This operates at 'n' times. In big O notation we say "O ( n )"

When we deal with for loops inside for loops we say that this is an exponential runtime.

See the following example of exponential runtime.

void printAll (char** c, int v, int u){

     for(i=0;i<v;i++){

          for(j=0;j<u;j++){

               cout << c[i] <<endl;

          }

     }

}

O (n ^ u )

The number of operations is n to the power of u.

Terminology:

• BIG O NOTATION: 
• This is the worse case runtime meaning that the function you are analysing can run much faster but this is the worse possible runtime.
• LITTLE O NOTATION:
• This is the best case runtime meaning that the function can not exceed this threshold.
• THATA:
•  This is when BIG O and LITTLE O are equivalent.

Notation Syntax:

big o:

O ( cost of function)

little o:

o ( cost of function)

infinity:

oo 

Thata:

O 

What is log?

Log is logarithm is the number of numbers we multiple to get another number.

See the following examples:

Log 4 = 2

Log 8 = 3

Log 16 = 4

Note: In computer science we usually like to use log as base 2.

Order from fastest to slowest:

c - constant

n*log ^n

n - linear

n^2 - quadratic

n^3 - cubic

2^n  

Why do we care about performance?

Any algorithm you run unless its C++ will be slow by default and as a programmer you need to make sure your applications are performant. We have big files and the more data we are processing the longer our programs will run.  

SEARCH Algorithms:

Linear Search

One of the most basic ways to search data is by using linear search. Start at 0 and compare one by one if the value is equal to the item which is being searched for.  

Binary Search

It is very easy to implement when the data is sorted. What do I mean by sorted?

For something to be sorted that means that their is a relationship for an element and another element:

• We are sorting least to greatest.
• If it's not bigger or smaller then its equal.
• You start from the middle of the list.

Simple example of sorting

var a[1,16,17,21,23,24,30,37,32,35,40,49,51,52,54,60];

var i=52;

if( i < a[a.length] && i > a[0] ) {

    var s1=a.split(0,(a.length/2));

    var s2=a.split((a.length/2));

}

Step 1:

• Check if the number is as big as the last number in the list or as small as the first number in the list.

Step 2:

• Split the list in half then test the last of the first split and the first of the second split are greater than or less then the number we are searching for.

Step 3:

• Repeat Step 2 until fail or success.

RECURSION:

Recursion is when you call the same function with the same function. There is a possibility of stack-overflow but in many cases you should know how much memory and resources you have available. In many cases stack-overflow happens when you have an infinite loop that is calling a function recursively until it reaches the limit of the stack.

The benefit of recursive functions however are that they makes problems easy to solve and program.

A good example of a recursive function is the Fibonacci Sequence.

Base Case: What ever this algorithm really needs to do.

Body: Effects other than base case.

//Example of function using recursion:

int fib( int n) {

     if(n<2) return 1;

     return fib(n-1)+fib(n+2);

}

//Example of equivalent code but without recursion:

int fibNoRecurse(int n){

     if(n < 2){

          return 1;

     }else{

          int n1=1;

          int n2=1;

          for(int i=2;i<=n;++i){

               int temp=n1;

               n1=n2;

               n2=n1+temp;

              

          }

          return n2;

     }

}

Note: When a function makes a call to another function. The function called makes a pointer in the call stack of where the code should return when the function is done, who the calle is.

The runtime stack is like a stack of plates. As each plate is pilled up one on top of the other it may reach its limit. For our kitchen its the roof. For a computer its the stack limit after you reach it you will get a stack overflow.

Can we check what the limit is for the stack? How do check the stack limit.

You can calculate how many bytes required to operate but many programmers that understand there stack and how its called often can overlook this unless they actually get a stack-overflow.

Note: Recursion is great for javascript or java because they have a virtual stack.