Knowledge Bank
  • My GitBook
  • Miscellaneous
  • Project
    • Rider and Intellij
    • Code
    • Frontend
      • Condition
      • AddConditionModalDialog
    • Backend
    • e2e
      • fragments
  • JAVASCRIPT
    • Promise
    • Destructuring
    • Spread Syntax and Rest Parameters
    • Typescript
      • Examples of Types
      • React Typescript
    • This
    • Dot Notation vs Bracket Notation
    • Shallow vs Deep Clone
    • New ES Edition
  • C#
    • Project Note
    • Basic
    • Shortcut and Debugging
  • Programming Paradigms
    • SOLID Principles
    • Object Oriented Programming (OOP)
      • Evolution of OOP (Procedural to OOP)
      • Instantiation
      • 4 Pillars of OOP
      • Extra
    • Functional Programming (FP)
      • Idempotent
      • Imperative vs Declarative
      • Immutability
      • High Order Function and Closure
      • Currying
      • Partial Application
      • Memoization and Caching
      • Compose and Pipe
      • Extra
      • Example of FP
    • OOP vs FP
      • Composition vs Inheritance
  • DATA STRUCTURE
    • Big O
    • Data Structure
    • Array
    • Hash Table
    • Linked List
    • Queue and Stack
    • Tree
      • Binary Heap
      • Trie
    • Graph
      • Example of Graph
  • React-Redux
    • MobX
    • Best Practices
  • Algorithms
    • Recursion
      • Examples of Recursion
    • Sorting
    • Searching and Traversal
    • Dynamic Programming
  • REFACTORING
    • Clean Code
      • Formatting
      • Error Handling
      • Concurrency
      • Testing
      • SOLID Principles
      • Classes
      • Objects and Data Structures
      • Variables
      • Functions
    • Code Smells
      • Long Function
      • Duplicate Code
      • Loops
      • Double Negative
      • Christmas Tree Code
      • Complex Condition
      • Primitive Obsession
      • Speculative Generality
      • God Class
      • Long Parameter List
  • Junior to Senior
    • AWS
      • Lambda
    • Session + Authentication
    • Redis
    • Kubernetes
      • Networking
      • Services
      • Deployment
      • Replica Set
      • YAML
      • pod-definition.yml
      • Kubectl
      • Pods
      • Fundamentals
    • Docker
      • Operating System - Extra
      • Dockerfile - Docker Image
      • Docker Storage
      • Docker Network
      • Docker Registry
      • Docker Command
      • Docker Compose
      • Docker Compose - Postgres
    • Security
      • Logging
      • HTTPS, Cross-Site-Scripting (XSS) and Cross-Site-Request-Forgery (CSRF)
      • 3rd Party Library
      • Injection
      • Code Secret, Secure Header, Access Control, Data Management, Authentication
    • CI/CD
    • SPA vs Server-Side Rendering
    • Performance
      • Optimized Code
      • Critical Render Path
      • Backend Optimization
      • Minimized Files and Images
      • Minimized Delivery
  • SECURITY
    • Encryption
    • SSH
  • Command
  • Cheatsheet
    • NPM
    • GIT
  • Writing Template
    • Guide
    • API
    • ChangeLog
    • FAQ
  • Linux
Powered by GitBook
On this page

Was this helpful?

  1. Algorithms

Searching and Traversal

Searching

  • Linear Search O(n)

Linear search is a method of finding a target value within the array using loop. Usually the data is unsorted

  • Binary Search O(log(n))

If our data is sorted, we can do better than O(n) because we essentially mimic the property of binary search trees where we can half the items instead of one at a time when looking for something. That is why storing data in a tree-like data structure is more efficient than a linear data structure like an array.

Traversal

Traversals simply means visiting every node and the operation is O(n) as we are visiting every single node. So how do we go about doing this in a data structure like a tree or graph? We use Breadth First Search and Depth First Search.

Breadth First Search

O(n) time complexity and O(n) space complexity where n is the breadth of the tree, because we use queue data structure

We go from root node, then the second level, the third level and so on from left to right. BFS uses additional memory because it is necessary to track every nodes and its child nodes in order on a given level.

Pros:

  • Shortest path - This is more apparent in Graph data structure where it is very good for finding the shortest path between a starting point and any other reachable node because we start off with the root node and then search the closest nodes first and then the node further without taking into account weight of the edges (the connection).

  • Closer node - If you know that the node is likely in the upper level of a tree, then BFS is better because it will search through the closest node first.

Cons:

  • More memory as we need to keep track of every nodes and its child nodes.

Depth First Search

O(n) time complexity and O(n) space complexity where n is the height of the tree, because we use stack data structure

The search follows one branch of the tree down as many levels as possible until the target notice found or the end is reached. When the search cannot go on any further, it continues at the nearest ancestor with an unexplored child. DFS has a lower memory requirement than BFS because it's not necessary to store all the nodes and its child nodes.

Pros:

  • Less Memory

  • Does path exist? Good at maze solving

Cons:

  • Can get slow if the tree or graph is really deep and it's not necessarily good at finding the shortest path.

Bellman-Ford and Dijkstra

It is algorithm to find the shortest path.

Pro of Bellman-Ford algorithm can accommodate negative weight VS Dijkstra which cannot do that.

Con of Bellman-Ford algorithm can take a long time to run in term of time complexity with O(n^2) on worst case scenario VS Dijkstra which is more efficient.

PreviousSortingNextDynamic Programming

Last updated 5 years ago

Was this helpful?