EP132: Big O Notation 101: The Secret to Writing Efficient Algorithms

EP132: Big O Notation 101: The Secret to Writing Efficient Algorithms

This week’s system design refresher:
͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­͏     ­
Forwarded this email? Subscribe here for more

This week’s system design refresher:

  • Big O Notation 101: The Secret to Writing Efficient Algorithms

  • Top 4 Forms of Authentication Mechanisms

  • 8 Key Concepts in DDD

  • Top 9 NoSQL Database Use Cases

  • SPONSOR US


Free tickets to P99 CONF - 60+ low-latency engineering talks (Sponsored)

P99 CONF is the technical conference for anyone who obsesses over high-performance, low-latency applications. Naturally, Rust is a core topic.

How is Rust being applied to solve today’s low latency challenges – and where it could be heading next? That’s what experts like Carl Lerche (Tokio creator, Rust contributor) and Ashley Williams (Rust core team, Rust Foundation founder) will be exploring.

Join 20K of your peers for an unprecedented opportunity to learn from engineers from Disney, Shopify, LinkedIn, Netflix, Google, Meta, Uber + more – for free, from anywhere.

GET YOUR FREE TICKET

Bonus: Registrants get 30-day free access to the complete O’Reilly library and a chance to win 1 of 500 swag packs!


Big O Notation 101: The Secret to Writing Efficient Algorithms

From simple array operations to complex sorting algorithms, understanding the Big O Notation is critical for building high-performance software solutions.

No alt text provided for this image
  1. O(1)
    This is the constant time notation. The runtime remains steady regardless of input size. For example, accessing an element in an array by index and inserting/deleting an element in a hash table.

  2. O(n)
    Linear time notation. The runtime grows in direct proportion to the input size. For example, finding the max or min element in an unsorted array.

  3. O(log n)
    Logarithmic time notation. The runtime increases slowly as the input grows. For example, a binary search on a sorted array and operations on balanced binary search trees.

  4. O(n^2)
    Quadratic time notation. The runtime grows exponentially with input size. For example, simple sorting algorithms like bubble sort, insertion sort, and selection sort.

  5. O(n^3)
    Cubic time notation. The runtime escalates rapidly as the input size increases. For example, multiplying two dense matrices using the naive algorithm.

  6. O(n logn)
    Linearithmic time notation. This is a blend of linear and logarithmic growth. For example, efficient sorting algorithms like merge sort, quick sort, and heap sort

  7. O(2^n)
    Exponential time notation. The runtime doubles with each new input element. For example, recursive algorithms solve problems by dividing them into multiple subproblems.

  8. O(n!)
    Factorial time notation. Runtime skyrockets with input size. For example, permutation-generation problems.

  9. O(sqrt(n))
    Square root time notation. Runtime increases relative to the input’s square root. For example, searching within a range such as the Sieve of Eratosthenes for finding all primes up to n.

Over to you: What else will you add to better understand the Big O Notation?


How to monitor a Next.js application with app-based router (Sponsored)

Next.js is a powerful JavaScript framework that offers optimized speed and performance for both development and runtime. In this blog post, you’ll learn how to set up application performance monitoring for the server side and browser monitoring for the frontend using the new App Router, giving you full-stack observability in your Next.js application. 

Get started for free


Top 4 Forms of Authentication Mechanisms

diagram, map
  1. SSH Keys:
    Cryptographic keys are used to access remote systems and servers securely

  2. OAuth Tokens:
    Tokens that provide limited access to user data on third-party applications

  3. SSL Certificates:
    Digital certificates ensure secure and encrypted communication between servers and clients

  4. Credentials:
    User authentication information is used to verify and grant access to various systems and services

Over to you: How do you manage those security keys? Is it a good idea to put them in a GitHub repository?


8 Key Concepts in DDD

No alternative text description for this image
  • Domain Driven Design
    Domain-driven design advocates driving the design of software through domain modeling.

    Unified language is one of the key concepts of domain-driven design. A domain model is a bridge across the business domains.

  • Business Entities
    The use of models can assist in expressing business concepts and knowledge and in guiding further development of software, such as databases, APIs, etc.

  • Model Boundaries
    Loose boundaries among sets of domain models are used to model business correlations.

  • Aggregation
    An Aggregate is a cluster of related objects (entities and value objects) that are treated as a single unit for the purpose of data changes.

  • Entities vs. Value Objects
    In addition to aggregate roots and entities, there are some models that look like disposable, they don't have their own ID to identify them, but are more as part of some entity that expresses a collection of several fields.

  • Operational Modeling
    In domain-driven design, in order to manipulate these models, there are a number of objects that act as "operators".

  • Layering the architecture
    In order to better organize the various objects in a project, we need to simplify the complexity of complex projects by layering them like a computer network.

  • Build the domain model
    Many methods have been invented to extract domain models from business knowledge.


Top 9 NoSQL Database Use Cases

Different databases excel in different areas and it’s important to choose the right database for the requirement.

No alternative text description for this image
  1. MongoDB (Document Store)
    Used for content management systems and catalog management. Features BSON format, schema-less design, supports horizontal scaling with sharding, and high availability with replication

  2. Cassandra (Wide-column Store)
    Ideal for time-series data management and recommendation engines. Offers wide-column format, distributed architecture, and CQL for SQL-like querying.

  3. Redis (Key-Value Store)
    Suited for Cache, Session Management, and Gaming Leaderboards. Provides in-memory storage, support for complex data structures, and persistence options with RDB and AOF.

  4. Couchbase (Document Store with Key-Value)
    Used for content management systems and e-commerce platforms. Combines key-value and document-based operations with memory-first architecture and cross-data center replication.

  5. Neo4j (Graph DB)
    Excellent for social networking and fraud detection. Features ACID compliance, index-free adjacency, Cypher Query Language, and HA cluster capabilities.

  6. Amazon DynamoDB (Key-Value and Document)
    Perfect for serverless and IoT applications. Supports both key-value and complex document data, managed by AWS, with features like partition data across nodes and DynamoDB streams.

  7. Apache Hbase (Wide-Column Store)
    Used for data warehouse and large-scale data processing. Modeled after Google’s Bigtable, offers Hadoop integration, auto-sharding, strong consistency, and region servers.

  8. Elasticsearch (Search Engine)
    Ideal for full-text search and log and event data analysis. Built on Apache Lucene, document-oriented, with sharding and replication capabilities, and a RESTful interface.

  9. CouchDB (Document Store)
    Suitable for mobile applications and CMS. Document-oriented, ensures data consistency without locking, supports eventual consistency, and uses a RESTful API.

Over to you: Which other NoSQL database would you add to the list?


SPONSOR US

Get your product in front of more than 1,000,000 tech professionals.

Our newsletter puts your products and services directly in front of an audience that matters - hundreds of thousands of engineering leaders and senior engineers - who have influence over significant tech decisions and big purchases.

Space Fills Up Fast - Reserve Today

Ad spots typically sell out about 4 weeks in advance. To ensure your ad reaches this influential audience, reserve your space now by emailing sponsorship@bytebytego.com

 
Like
Comment
Restack
 

© 2024 ByteByteGo
548 Market Street PMB 72296, San Francisco, CA 94104
Unsubscribe

Get the appStart writing


by "ByteByteGo" <bytebytego@substack.com> - 11:35 - 5 Oct 2024