DEV Community


Posted on

Data Structures and Big(o)

Hello my fellow people once again, I wanted to cover Big(o) and its relation to data structures. If you read my previous post you should know the different types of data structures, what data structures are and how we use them. You should also have a good idea of what time complexity(Big(o)) is. If not, you can read them again here:

otherwise, lets review quickly. data structures are a way for us to have a management system for storing and maintain our data.

Linear: arrays, lists
Tree: binary, heaps, space partitioning etc.
Hash: distributed hash table, hash tree etc.
Graphs: decision, directed, acyclic etc." (2017-2020 integralist)

Time complexity is an analysis used in programming to time how long it takes to run an algorithm given a number of inputs(n), as well as how long it takes to complete the task. Usually often referred to as Big-O notation, here is a list of common time complexities used with definitions.

"O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
O(n) — Linear Time: The number of of steps required are directly related (1 to 1).
O(n²) — Quadratic Time: The number of steps it takes to accomplish a task is square of n.
O(C^n) — Exponential: The number of steps it takes to accomplish a task is a constant to the n power (pretty large number)."
(freecodecamp, Algorithms in plain English: time complexity and Big-O notation, 2016

Ok, cool! Now lets get started. So, how do these two subjects come two in two? Well, determining what method you'll be using, access, search, insertion, or deletion. Each have an estimated time complexity. Generally, its best to go with a "worst case scenario" when finding the time complexity for an algorithm that way you know what's the worst possible time it takes for the algorithm to run. The image I have attached is a cheat sheet that I refer to at times, I attached it instead of writing down all of the different part. I feel it would make more sense to look at the color coordination than black and white, eezy-peezy-lemon-squeezy!

Alt Text

Thank you for reading my article, if I should clarify or go over with more details on a certain subject please let me know or if you think I should update or change any information, please leave a comment I am always willing to learn new things daily.

Discussion (0)