ArcTouch
Published in

ArcTouch

Data Structure 101: Part 2

This is the 2nd post in a series about Data Structures.

In Part 1 we learned the importance of studying Data Structure. In this post we will learn how to evaluate Data Structures and algorithms.

What is Cyclomatic Complexity?

Cyclomatic Complexity (CC) is a metric used to calculate the "time" an algorithm takes to complete its interactions. The word time is in quotes because it isn't exactly the time in seconds, but the number of commands, function, modules, and conditions an algorithm will take to complete a linear path.

Try to imagine you want your code to get all links from a page, and then open a new tab with all the links you got. To simplify, here is the code:

A control flow chart for this example is:

Flow chart containing the logic described above

With this in mind, you can calculate the CC byfollowing this formula:
M = E — N + 2P
Where:
- E: Number of the edges in the chart
- N: Number of the nodes in the chart
- P: Number of connected components in the chart

In the flow chart above we have:
E = 5
N = 5
P = 1

So, M = 5 — 5 + 2 = 2;

You might be thinking, "Okay, but what do I do with that number?"

The result for M shows if your code needs to be prioritized for refactoring.

≤4: is considered good
≥5 & ≤7: is considered medium
≥8 & ≤10: is considered high
≥11: something is really wrong here

If you need to refactor, try creating the CC score for its routines first. It's helpful to know where to start, and know if you made progress. You can compare the before and after, and see the improvements made.

There are other metrics to measure complexity.

One of my favorites is Time complexity.

What is Time Complexity?

Time Complexity (TC) is somewhat more straightforward. As the name suggests, it uses time as the main metric, but it’s computer time, calculated by the number of operations performed by an individual algorithm. Since we have a lot of variability involved in an algorithm, going all the way from the input we receive to the conditions we have, we use three cases, the worst case, the best case, and the medium case.

Using the code shown before, let's try to figure out what those cases are by example. The concept for the best case is what input must be given to the algorithm to finish running and consuming the fewest amount of computational time. In the algorithm given above, the best case is to have no link because you will look for links in the DOM, and skip the for loop.

And the worst case? This would be a huge number of links so the code will take forever to complete (and probably crash the browser). And the medium case is somewhere between these extremes.

Time Complexity usually uses Big O notation. The Big O notation uses N as the input, and for the Time Complexity, the worst-case is used to summarize an algorithm. For the example shown above, the category of the algorithm is O(n) because it will run for each element in the input. If you have any questions about Big O notation, leave a comment and I’ll respond.

In a future post I intend to give some more examples.

Conclusion

In this post we learned two essential concepts about Data Structures. If you have anything you want to see in future posts, please leave a comment.

Here at ArcTouch we have a great team of software developers. If you’d like to join us, check out our career opportunities.

--

--

--

We help companies forge meaningful connections with their customers, partners and employees through lovable apps, websites and other innovative digital products.

Recommended from Medium

“Iowa, What the Hell Happened?”

The Microservice Approach to Building Scaleable Applications — Part One

A method to using Git for Learn.co lessons

Create ASP.NET Core CRUD Web API with the Repository pattern

2022 March, April update plan

No Code in The Wild at a Newspaper

Spark: Databricks: How to get the current notebook path?

A big circle of darkness

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
João Marcus Fernandes

João Marcus Fernandes

Software Engineer at ArcTouch

More from Medium

ROLE OF STACK AND QUEUES IN PROBLEM SOLVING

Leetcode Easy: Binary Tree Inorder Traversal

Binary tree with a root of one. No left node, right node of 2.Node 2 has a left node of 3

LeetCode — First Bad Version

Leetcode — Add Digits — Easy