DEV Community: GeekDroiD

Understanding Big O Notation

GeekDroiD — Sun, 03 Jul 2022 22:02:56 +0000

What is Big O Notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

— Wikipedia’s definition of Big O notation

In simple words, Big O notation describes the complexity of your code using algebraic terms.

To understand what Big O notation is, we can take a look at a typical example, O(n²), which is usually pronounced “Big O squared”. The letter “n” here represents the input size, and the function “g(n) = n²” inside the “O()” gives us an idea of how complex the algorithm is with respect to the input size.

An Algorithm is a piece of code that takes N steps to solve a problem so we can label an algorithm as 50-step algorithm or another as 2000-step algorithm right? actually yes we can if the input for the algorithm is static but if the input for the algorithm varies the number of steps the algorithm takes is going to change and this happens the most of time here is where Big O Notation is really useful.

Here’s what the notation means. It expresses the answer to what we’ll call the “key question.” The key question is: if there are N data elements, how many steps will the algorithm take? Go ahead and read that sentence again. Then, emblazon it on your forehead, as this is the definition of Big O Notation that we’ll be using throughout the rest of our programming life.

The answer to the key question lies within the parentheses of any Big O expression. for example O(N) says that the answer to the key question is that the algorithm will take N steps, therefore, the expression O(n²) says that the answer to the key question is that the algorithm will take N^2 steps which is pronounced “Big O squared”.

Here is which function grows faster than the others.

When we calculate big O notation, we only care about the dominant terms, and we do not care about the coefficients.

Short history about how important is Big O in real life

Once upon a time there was an Indian king who wanted to reward a wise man for his excellence. The wise man asked for nothing but some wheat that would fill up a chess board.

But here were his rules: in the first tile he wants 1 grain of wheat, then 2 on the second tile, then 4 on the next one…each tile on the chess board needed to be filled by double the amount of grains as the previous one. The naïve king agreed without hesitation, thinking it would be a trivial demand to fulfill, until he actually went on and tried it…

So how many grains of wheat does the king owe the wise man? We know that a chess board has 8 squares by 8 squares, which totals 64 tiles, so the final tile should have 2⁶⁴ grains of wheat. If you do a calculation online, you will end up getting 1.8446744*10¹⁹, that is about 18 followed by 18 zeroes. Assuming that each grain of wheat weights 0.01 grams, that gives us 184,467,440,737 tons of wheat. And 184 billion tons is quite a lot, isn’t it?

The numbers grow quite fast later for exponential growth don’t they? The same logic goes for computer algorithms. If the required efforts to accomplish a task grow exponentially with respect to the input size, it can end up becoming enormously large.

Now the square of 64 is 4096. If you add that number to 2⁶⁴, it will be lost outside the significant digits. This is why, when we look at the growth rate, we only care about the dominant terms. And since we want to analyze the growth with respect to the input size, the coefficients which only multiply the number rather than growing with the input size do not contain useful information.

The Soul of Big O

Now that we’ve encountered O(N) and O(1), we begin to see that Big O Notation does more than simply describe the number of steps an algorithm takes, such as with a hard number like 22 or 400. Rather, it’s an answer to that key question on your forehead: if there are N data elements, how many steps will the algorithm take?

While that key question is indeed the strict definition of Big O, there’s actually more to Big O than meets the eye.

Let’s say we have an algorithm that always takes three steps no matter how much data there is. That is, for N elements, the algorithm always takes three steps. How would you express that in terms of Big O?

Based on everything you’ve learned up to this point, you’d probably say that it’s O(3).

However, it’s actually O(1). And that’s because of the next layer of understanding Big O, which I will reveal now.

While Big O is an expression of the number of an algorithm’s steps relative to N data elements, that alone misses the deeper why behind Big O, what it's called the “soul of Big O.”

The soul of Big O is what Big O is truly concerned about: how will an algorithm’s performance change as the data increases?

This is the soul of Big O. Big O doesn’t want to simply tell you how many steps an algorithm takes. It wants to tell you the story of how the number of steps increase as the data changes.

Viewed with this lens, we don’t care very much whether an algorithm is O(1) or O(3). Because both algorithms are the type that aren’t affected by increased data, as their number of steps remain constant, they’re essentially the same kind of algorithm. They’re both algorithms whose steps remain constant irrespective of the data, and we don’t care to make a distinction between the two.

An algorithm that is O(N), on the other hand, is a different type of algorithm. It’s an algorithm whose performance is affected as we increase the data. More specifically, it’s the kind of algorithm whose steps increase in direct proportion to the data as the data increases. This is the story O(N) tells. It tells you about the proportional relationship between the data and the algorithm’s efficiency. It describes exactly how the number of steps increase as the data increases.

I hope you guys found this resume helpful for build new high performance algorithms! 🤓🧐

Why Data Structures and Algorithms are important

GeekDroiD — Wed, 18 May 2022 21:11:49 +0000

For years I have been wordering how a one-dimensional array actually works in memory (one of the most basic data structures in computer science) and when I started to read books about Data structures and Algorithms I found that a computer's memory can be viewed as a giant collection of cells and when a program declares an array, it allocates a contiguous set of empty cells for use in the program. So, if you were creating an array meant to hold five elements, your computer would find a group of five empty cells in a row and designate it to serve as your array:

That inspired me to learn more Data Structures because I can know how works what I'm using everyday to build better products.

Even a process as simple as preparing a bowl of cereal is technically an algorithm, as it involves following a defined set of steps to achieve the task at hand. The cereal-preparation algorithm follows these four steps (for me, at least):

Grab a bowl.
Pour cereal into the bowl.
Pour milk into the bowl.
Dip a spoon into the bowl.
Enjoy 😋

There are Data structures such as LinkedList, Stack, Queues, HashTable, Tree, Graph that help us to build better products for millions of users.

Example of the importance of each data structure:

HASH TABLE

Imagine you’re writing a program that allows customers to order fast food from a restaurant, and you’re implementing a menu of foods with their respective prices. You could, technically, use an array:

menu = [ ["french fries", 0.75], ["hamburger", 2.5], ["hot dog", 1.5], ["soda", 0.6] ]

This array contains several subarrays, and each subarray contains two elements. The first element is a string representing the food on the menu, and the second element represents the price of that food.

if this array were unordered, searching for the price of a given food would take O(N) steps since the computer would have to perform a linear search. If it’s an ordered array, the computer could do a binary search, which would take O(log N).

while O(log N) isn’t bad, we can do better. In fact, we can do much better. the data structure called hash table can be used to look up data in just O(1) time. By knowing how hash tables work under the hood and the right places to use them, you can leverage their tremendous lookup speeds in many situations.

LINKEDLIST

The data from linked lists can be scattered across different cells throughout the computer’s memory.

Connected data that is dispersed throughout memory are known as nodes. In a linked list, each node represents one item in the list. The big question, then, is: if the nodes are not next to each other in memory, how does the computer know which nodes are part of the same linked list?

This is the key to the linked list: each node also comes with a little extra information, namely, the memory address of the next node in the list. This extra piece of data—this pointer to the next node’s memory address—is known as a link. Here is a visual depiction of a linked list:

In this example, we have a linked list that contains four pieces of data: "a", "b", "c", and "d". However, it uses eight cells of memory to store this data, because each node consists of two memory cells. The first cell holds the actual data, while the second cell serves as a link that indicates where in memory the next node begins. The final node’s link contains null since the
linked list ends there.

(A linked list’s first node can also be referred to as its head, and its final node as its tail.)

The fact that a linked list’s data can be spread throughout the computer’s memory is a potential advantage it has over the array. An array, by contrast, needs to find an entire block of contiguous cells to store its data, which can get increasingly difficult as the array size grows.

STACK

A stack stores data in the same way arrays do—it’s simply a list of elements.

The one catch is that stacks have the following three constraints:
• Data can be inserted only at the end of a stack.
• Data can be deleted only from the end of a stack.
• Only the last element of a stack can be read.

You can think of a stack as an actual stack of dishes; you can’t look at the face of any dish other than the one at the top. Similarly, you can’t add any dish except to the top of the stack, nor can you remove any dish besides the one at the top. (At least, you shouldn’t.) In fact, most computer science literature refers to the end of the stack as its top, and the beginning of the stack
as its bottom.

this diagrams will reflect this terminology by viewing stacks as vertical arrays,

Stacks are useful for undo\redo operation in word processors, Expression evaluation and syntax parsing, many virtual machines like JVM are stack oriented.

QUEUE

You can think of a queue as a line of people at the movie theater. The first one in the line is the first one to leave the line and enter the theater. With queues, the first item added to the queue is the first item to be removed. That’s why computer scientists apply the acronym “FIFO” to queues: First In, First Out.

As with a line of people, a queue is usually depicted horizontally. It’s also common to refer to the beginning of the queue as its front, and the end of the queue as its back.

Queues are arrays with three restrictions:
• Data can be inserted only at the end of a queue.
• Data can be deleted only from the front of a queue.
• Only the element at the front of a queue can be read.

Queues are useful for transport and operations research where various entities are stored and held to be processed later in the queue performs the function of a buffer.

also exists priority queues where is helpful is in an application that manages the triage system for a hospital emergency room. In the Emergency, we don’t treat people strictly in the order in which they arrived. Instead, we treat people in the order of the severity of their symptoms. If someone suddenly arrives with a life-threatening injury, that patient will be placed at the front of the queue, even if the person with the flu had arrived hours earlier.

Let’s say our triage system ranked the severity of a patient’s condition on a scale of 1 to 10, with 10 being the most critical. Our priority queue may look like this:

In determining the next patient to treat, we will always select the patient at the front of the priority queue, since that person’s need is the most urgent. In this case, the next patient we’d treat is Patient C.

If a new patient now arrives with a condition severity of 3, we’ll initially place this patient at the appropriate spot within the priority queue. We’ll call this person Patient E:

TRIE

Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.

Like most other trees, the trie is a collection of nodes that point to other nodes. However, the trie is not a binary tree. Whereas a binary tree doesn’t allow any node to have more than two child nodes, a trie node can have any number of child nodes

There are many types of trees and maybe you have used it the DOMAIN OBJECT MODEL(DOM) tree, File System Tree in your computer and even OBJECT ORIENTED PROGRAMMING(OOP) inheritance is a tree, these are unordered trees and Fibonacci Tree, Binomial tree, binary tree are examples of ordered trees

Exists many applications for trees:

Heap is a tree data structure which is implemented using arrays and used to implement priority queues.
B-Tree and B+ Tree: They are used to implement indexing in databases.
Syntax Tree: Used in Compilers.
K-D Tree: A space partitioning tree used to organize points in K dimensional space.
Trie: Used to implement dictionaries with prefix lookup.
Suffix Tree: For quick pattern searching in a fixed text.
Manipulate hierarchical data.
Make information easy to search (tree traversal).
Manipulate sorted lists of data.
As a workflow for compositing digital images for visual effects.
Router algorithms.

GRAPH

A data is a non-linear and abstract data structure it is defined by this behavior and not by the underlying mathematical model, it consists of a set of nodes also known as vertices, these nodes are connected by edges, a graph can be direct and indirect.

A graph is a data structure that specializes in relationships, as it easily conveys how data is connected.

Here is a visualization of our social network, displayed as a graph:

Each person is represented by a node, and each line indicates a friendship with another person. If you look at Alice, for example, you can see that she is friends with Bob, Diana, and Fred, since her node has lines that connect to their nodes.

Graphs are helpful for connections/relations in social networking sites, Routing, networks of communication, data organization, etc.

In computer science graph theory is used for the study of algorithms like:

Dijkstra's Algorithm
Prims's Algorithm
Kruskal's Algorithm
Graphs are used to define the flow of computation.
Graphs are used to represent networks of communication.
Graphs are used to represent data organization.
Graph transformation systems work on rule-based in-memory manipulation of graphs. Graph databases ensure transaction-safe, persistent storing and querying of graph structured data.
Graph theory is used to find shortest path in road or a network.
In Google Maps, various locations are represented as vertices or nodes and the roads are represented as edges and graph theory is used to find the shortest path between two nodes.

At the end each Data Structures has a reason why they exists.

Suppose you are working in a Facebook company. You come up with an optimal solution of a problem (like sorting a list of users from India) with time complexity of O(n Log n) instead of O(n^2) and assume that n for the problem here for the company in real life scenario is 100 million (very fair assumption considering the number of users registered on Facebook exceeds 1 billion). n Log n would be 800 million, while n^2 would be 10^7 billion. In cost terms, you can see that the efficiency has been improved more than 10^7 times, which could be a huge saving in terms of server cost and time.

Now you might have got that companies want to hire a smart developer who can make the right decision and save company resources, time, and money. So before you give the solution to use a Hash table instead of List to solve a specific problem think about the big scale and all the case scenarios carefully. It can generate revenue for the company or the company can lose a huge amount of money.

I hope you guys found this resume helpful 🤓🧐