Intro to DSA & Big O Notation

Notes to master DSA:

Master DSA to be "eligible" for high paying salaries offered to S/w Ers.
DSA is the major chunk of Software Engineering.
Before writing code, make sure you understand the bigger picture and then drill down into details.
Its all about understanding the concepts visually, and then translating those concepts into code via any l/g as DSA is language agnostic.
Every upcoming concept is somehow linked to previous concepts. Hence, don't hop topics or move forward unless you have mastered the concept thoroughly by practicing it.
When we learn concepts visually, we get deeper understanding of the material which inturn helps us to retain the knowledge for longer duration.
If you follow these advices, you'll have nothing to lose.

Linear DS:
Arrays
LinkedList(LL) & Doubly LL (DLL)
Stack
Queue & Circular Queue

Non-linear DS:
Trees
Graphs

Big O Notation

It is essential to understand this notation for perf comparison of algos.
Its a mathematical way for comparing efficiency of algos.

Time Complexity

The faster the code runs, the lower it will be
V. impt for most of the interviews.

Space Complexity

Considered rarely as compared to time complexity due to low storage cost.
Need to be understood, as an interviewer may ask you from this also.

Three Greek Letters:

1. Omega
2. Theta
3. Omicron i.e Big-O [seen most often]

Cases for algo

1. Best case [represented using Omega]
2. Avg case [represented using Theta]
3. Worst case [represented using Omicron]

Technically there is no best case of avg case Big-O. They are denoted using omega & theta respectively.
We are always measuring worst case.

## O(n): Efficient Code
Proportional
Its simplified by dropping the constant values.
An operation happens 'n' times, where n is passed as an argument as shown below.
Always going to be a straight line having slope 1, as no of operations is proportional to n.
X axis - value of n.
Y axis - no of operations 

// O(n)
function printItems(n){
  for(let i=1; i<=n; i++){
    console.log(i);
  }
}
printItems(9);

// O(n) + O(n) i.e O(2n) operations. As we drop constants, it eventually becomes O(n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(i);
  }
  for(let j=0; j<n; j++){
    console.log(j);
  }
}
printItems(10);

## O(n^2):
Nested loops.
No of items which are output in this case are n*n for a 'n' input.
function printItems(n){
  for(let i=0; i<n; i++){
    console.log('\n');
    for(let j=0; j<n; j++){
      console.log(i, j);
    }
  }
}
printItems(4);

## O(n^3):
No of items which are output in this case are n*n*n for a 'n' input.
// O(n*n*n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(`Outer Iteration ${i}`);
    for(let j=0; j<n; j++){
      console.log(`  Mid Iteration ${j}`);
      for(let k=0; k<n; k++){
        //console.log("Inner");
        console.log(`    Inner Iteration ${i} ${j} ${k}`);
      }
    }
  }
}
printItems(3);


## Comparison of Time Complexity:
O(n) > O(n*n)


## Drop non-dominants:
function xxx(){
  // O(n*n)
  Nested for loop

  // O(n)
  Single for loop
}
Complexity for the below code will O(n*n) + O(n) 
By dropping non-dominants, it will become O(n*n) 
As O(n) will be negligible as the n value grows. O(n*n) is dominant term, O(n) is non-dominnat term here.

## O(1):
Referred as Constant time i.e No of operations do not change as 'n' changes.
Single operation irrespective of no of operands.
MOST EFFICIENT. Nothing is more efficient than this. 
Its a flat line overlapping x-axis on graph.


// O(1)
function printItems(n){
  return n+n+n+n;
}
printItems(3);


## Comparison of Time Complexity:
O(1) > O(n) > O(n*n)

## O(log n)
Divide and conquer technique.
Partitioning into halves until goal is achieved.

log(base2) of 8 = 3 i.e we are basically saying 2 to what power is 8. That power denotes the no of operations to get to the result.

Also, to put it in another way we can say how many times we need to divide 8 into halves(this makes base 2 for logarithmic operation) to get to the single resulting target item which is 3.

Ex. Amazing application is say for a 1,000,000,000 array size, how many times we need to cut to get to the target item.
log(base 2) 1,000,000,000 = 31 times
i.e 2^31 will make us reach the target item.

Hence, if we do the search in linear fashion then we need to scan for billion items in the array.
But if we use divide & conquer approach, we can find it in just 31 steps.
This is the immense power of O(log n)

## Comparison of Time Complexity:
O(1) > O(log n) > O(n) > O(n*n)
Best is O(1) or O(log n)
Acceptable is O(n)

O(n log n) : 
Used in some sorting Algos.
Most efficient sorting algo we can make unless we are sorting only nums.

Tricky Interview Ques: Different Terms for Inputs.
function printItems(a,b){
  // O(a)
  for(let i=0; i<a; i++){
    console.log(i);
  }
  // O(b)
  for(let j=0; j<b; j++){
    console.log(j);
  }
}
printItems(3,5);

O(a) + O(b) we can't have both variables equal to 'n'. Suppose a is 1 and b is 1bn.
Then both will be very different. Hence, it will eventually be O(a + b) is what can call it.
Similarly if these were nested for loops, then it will become O(a * b)

## Arrays
No reindexing is required in arrays for push-pop operations. Hence both are O(1).
Adding-Removing from end in array is O(1)

Reindexing is required in arrays for shift-unshift operations. Hence, both are O(n) operations, where n is no of items in the array.
Adding-Removing from front in array is O(n)

Inserting anywhere in array except start and end positions:
myArr.splice(indexForOperation, itemsToBeRemoved, ContentTobeInsterted)
Remaining array after the items has to be reindexed.
Hence, it will be O(n) and not O(0.5 n) as Big-O always meassures worst case, and not avg case. 0.5 is constant, hence its droppped.
Same is applicable for removing an item from an array also as the items after it has to be reindexed.


Finding an item in an array:
if its by value: O(n)
if its by index: O(1)

Select a DS based on the use-case.
For index based, array will be a great choice.
If a lot of insertion-deletion is perform in the begin, then use some other DS as reindexing will make it slow.

Comparison of Time Complexity for n=100:

O(1) = 1
O(log 100) = 7
O(100) = 100
O(n^2) = 10,000

Comparison of Time Complexity for n=1000:

O(1) = 1
O(log 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1,000,000

Mainly we will focus on these 4:
Big O(n*n): Nested Loops
Big O(n): Proportional
Big O(log n): Divide & conquer
Big O(1): Constant

O(n!) usually happens when we deliberately write bad code.
O(n*n) is horrible Algo
O(n log n) is acceptable and used by certain sorting algos
O(n) : Acceptable
O(log n), O(1) : Best

Space complexity is almost same for all DS i.e O(n).
Space complexity will vary from O(n) to O(log n) or O(1) with sorting algos

Time complexity is what varies based on algo

Best time complexity for sorting other than numbers like string is O(n log n) which is in Quick, Merge, Time, heap sorts.

Best way to apply your learning is to code as much as you can.

Selecting which DS to choose in which problem statement based on Pros-Cons of each DS.

For more info, refer to: bigocheatsheet.com

The above is the detailed content of Intro to DSA & Big O Notation. For more information, please follow other related articles on the PHP Chinese website!