Notas para dominar DSA:

Master DSA será "elegible" para recibir salarios altos ofrecidos a S/w Ers.
DSA es la parte principal de la ingeniería de software.
Antes de escribir código, asegúrese de comprender el panorama general y luego profundice en los detalles.
Se trata de comprender los conceptos visualmente y luego traducirlos a código mediante cualquier l/g, ya que DSA es independiente del idioma.
Cada concepto próximo está de alguna manera vinculado a conceptos anteriores. Por lo tanto, no salte de tema ni avance a menos que haya dominado completamente el concepto practicándolo.
Cuando aprendemos conceptos visualmente, obtenemos una comprensión más profunda del material, lo que a su vez nos ayuda a retener el conocimiento durante más tiempo.
Si sigues estos consejos no tendrás nada que perder.

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

Non-linear DS:
Trees
Graphs

Notación O grande

Es esencial comprender esta notación para comparar el rendimiento de algos.
Es una forma matemática de comparar la eficiencia de algos.

Complejidad del tiempo

Cuanto más rápido se ejecute el código, menor será
V. impt para la mayoría de las entrevistas.

Complejidad espacial

Rara vez se considera en comparación con la complejidad del tiempo debido al bajo costo de almacenamiento.
Debe entenderse, ya que un entrevistador también puede preguntarle sobre esto.

Tres letras griegas:

1. Omega
2. Theta
3. Omicron, es decir, Big-O [visto con mayor frecuencia]

Casos para algo

1. Mejor caso [representado usando Omega]
2. Caso promedio [representado usando Theta]
3. Peor caso [representado mediante Omicron]

Técnicamente, no existe el mejor caso de caso promedio Big-O. Se indican usando omega y theta respectivamente.
Siempre estamos midiendo el peor de los casos.

## 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





## 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





## 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 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





## 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.





  
  
  Comparación de la complejidad del tiempo para n=100:


O(1) = 1

O(registro 100) = 7

O(100) = 100

O(n^2) = 10,000


  
  
  Comparación de la complejidad del tiempo para n=1000:


O(1) = 1

O(registro 1000) = ~10

O(1000) = 1000

O(1000*1000) = 1.000.000

Principalmente nos centraremos en estos 4:

Big O(n*n): Bucles anidados

Gran O(n): Proporcional

Big O (log n): divide y vencerás

Gran O(1): Constante

O(n!) suele ocurrir cuando escribimos código incorrecto deliberadamente.

O(n*n) es horrible Algo

O(n log n) es aceptable y utilizado por ciertos algoritmos de clasificación

O(n): Aceptable

O(log n), O(1): Mejor

 La complejidad del espacio es casi la misma para todos los DS, es decir, O (n). 

La complejidad del espacio variará de O(n) a O(log n) u O(1) con algoritmos de clasificación

La complejidad del tiempo es lo que varía según el algoritmo

La mejor complejidad de tiempo para ordenar cosas que no sean números como cadenas es O(n log n), que se encuentra en ordenamiento rápido, combinación, tiempo y montón.


  
  
  La mejor manera de aplicar tu aprendizaje es codificar tanto como puedas.


Seleccionar qué DS elegir en qué planteamiento del problema en función de los pros y los contras de cada DS.

Para obtener más información, consulte: bigocheatsheet.com