Big O - Cheat Sheet

Going to make myself a personal copy of a Big O cheat sheet, and try to explain why each data structure has certain properties to be a refresher for my data structure.

Array (Dynamic)

Access - O(1)

Array's have quick access to a specified index because arrays take a finite contiguous block or memory that can be used to pinpoint memory locations.

Search - O(n)

Array's have linear time search because there are no special properties to indicate the value you are trying to look for, therefore you have to search through the elements individually.

Insertion - O(n)

Array's take up a contiguous block of memory, therefore when a new element is added to the list, it must be recreated, and/or the elements may be shifted.

Deletion - O(n)

Same as insertion in that it takes a contiguous block of memory, and therefore needs to be shifted.

Space - O(n)

Requires as much space as elements

Stack

Access -  O(n)

Must traverse through the top reference to get to index.

Search - O(n)

Must traverse through top reference to get to search value.

Insertion - O(1)

All you need to do is change reference links.

Deletion - O(1)

All you need to do is change the reference links.

Space - O(n)

Takes up as much space as its elements.

Queue

Access -  O(n)

Must traverse through the head/tail reference to get to index.

Search - O(n)

Must traverse through head/tail reference to get to search value.

Insertion - O(1)

All you need to do is change reference links.

Deletion - O(1)

All you need to do is change the reference links.

Space - O(n)

Takes up as much space as its elements.

Hashtable

Access - N/A

There is no concept of indexes in hashtables. 

Search - Average O(1), Worst O(n)

Searching is quick because of hash function computation.

Insertion - Average O(1), Worst O(n)

Hashtables know where to add elements from the hash function, but there is a possibility to hashing strategy by have worst case collisions.

Deletion - Average O(1), Worst O(n)

Hashtables know where to delete elements from the hash function, but there is a possibility to hashing strategy by have worst case collisions.

Space - O(n)

Hashtables take up as much space as its elements.

Binary Search Tree

Access - Average O(log n), Worst O(n)

Tree structure allows you to traverse a tree in log n fashion.

Search - Average O(log n), Worst O(n)

Tree structure allows you to traverse a tree in log n fashion.

Insertion - Average O(log n), Worst O(n)

Tree structure allows you to traverse a tree in log n fashion.

Deletion - Average O(log n), Worst O(n)

Tree structure allows you to traverse a tree in log n fashion.

Space - O(n)

Takes up as much space as its elements

Comments

Post a Comment

Popular posts from this blog

Uncle Bob's Clean Architecture

Image
The basis of my current understanding of architecture comes from the brilliant mind of Robert C. Martin (Uncle Bob). You can find the original post through his blog , which I strongly encourage you to read. In this post I'll try to summarize some of the key points I've understood from his post. Clean Architecture Source Clean architecture is a design used to emphasize the structure and relation of your various code components to promote the idea of Dependency Rule , such that "source code dependencies only point inwards" . Clean architecture is able to promote this by defining that your software system consists of various layers , that can be organized in such a way that the layers point in one direction, and a dependency graph will not have circular reference. The reason this is important is because it allows you to keep closely code related, and increase clarity of how components fit into your system. Explaining the Layers We can really separate out this
Read more

C4 Model: Describing Software Architecture

Image
The point behind a presentation of Visualizing Software Architecture , by Simon Brown, was that we need to standardize the way software developers communicate with each other in respect to our discussions of software architecture. As part of Simon's consultation, one exercise he gave to software architects was a simple task to white board the architecture of a software system. The results he received varied immensely, and there was never a defacto standard format that he received from this exercise. When inspecting the feedback from the participants, the general answer was that it was easy to come up with the design, but difficult to properly put their ideas onto paper, or white board in this case. White Board Example, c4model.com Simon sought to start a movement by defining a set of organizational rules to help us describe our software architecture with a set of standard terminologies. His work has let to C4 Model , which stands for C ontext, C ontainers, C omponents,
Read more

Multi-Tenant Design: The Basics

Image
As your software system begins to grow and become a successful, you may find yourself at a place where you will want to monetize your software by allowing other companies to use it. One such design that will come in handy is called the Multi-Tenant design, and it allows you to license your software to other companies, allowing them to use your software system for through some contract. You manage the system, and they are merely an entity within it, a tenant. Source At its core, a multi-tenant design is driven by the idea that each tenant contains an identifier, which is then passed through with each request or action. By including this information, the system will know what behavior or data set to pull from. Traditionally the tenant identifier is GUID  that is transferred through HTTP requests as a HTTP header, x-tenant-id . The value is then kept within the thread context, and used to determine the configuration of a request, as well as the data it can access. Data should ei
Read more