Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structures - Coggle Diagram
Data Structures
Algorithmic Efficiency
Big O
-
-
-
-
How do we calculate it
1- add all steps: O(a) + O(b) == O(a+b)
2 - drop constants O(2N) is the same as O(N) because time growth linear
3 - Different input, different variables O(a*b) in case of for loop inside of another for loop with different arrays
4 - Drop non dominant terms O(n+n^2) -> O(n^2) because that is what drives time change
-
-
We can use big O notation to talk not only about time but also about space. Some algorithms can gain speed by storing big datasets in memory. They might be big O of a small function for runtime but big O of a larger function for memory requirements
-
-
-
-
-
-
-
Liniar
-
Stack
-
-
-
Each time we add data to stack current Head is assigned to New Node Next and Head is set to new node
Sorting
Insertion Sort
This method relies on looking at each item in a list one at a time and inserting it into a new list that ends up being correctly sorted
Merge Sort
divide and conquer algorithm. We start with a large, unsorted list. Then we split that list repeatedly into smaller and smaller chunks (the dividing) until we end up with sorted (conquered) one-item lists, and then we simply merge them back together
-
-
-