<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Guilherme Luís Dall&#39;Agnol on Medium]]></title>
        <description><![CDATA[Stories by Guilherme Luís Dall&#39;Agnol on Medium]]></description>
        <link>https://medium.com/@guilhermeluisd?source=rss-954879e9e77------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*PQCD1Tb7wA3TK2DBsWrzAA.jpeg</url>
            <title>Stories by Guilherme Luís Dall&amp;#39;Agnol on Medium</title>
            <link>https://medium.com/@guilhermeluisd?source=rss-954879e9e77------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 23:28:13 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@guilhermeluisd/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Creating a virtual machine on AWS for free.]]></title>
            <link>https://medium.com/@guilhermeluisd/creating-a-virtual-machine-in-aws-for-free-394330a63ea?source=rss-954879e9e77------2</link>
            <guid isPermaLink="false">https://medium.com/p/394330a63ea</guid>
            <category><![CDATA[infrastructure]]></category>
            <category><![CDATA[virtual-machine]]></category>
            <category><![CDATA[ec2]]></category>
            <category><![CDATA[aws]]></category>
            <category><![CDATA[cloud]]></category>
            <dc:creator><![CDATA[Guilherme Luís Dall'Agnol]]></dc:creator>
            <pubDate>Sun, 06 Feb 2022 02:10:44 GMT</pubDate>
            <atom:updated>2022-02-06T11:52:12.656Z</atom:updated>
            <content:encoded><![CDATA[<p>Hello everybody, today we are going to see how to create a virtual machine for free.</p><p>What is a virtual machine? It’s a machine which is emulated inside another operational system.</p><p>First of all, you will be required to have an account on AWS, to create an account you can follow <a href="https://aws.amazon.com/premiumsupport/knowledge-center/create-and-activate-aws-account/">this</a> tutorial.</p><p>Assuming that you have successfully created an account , you have to login into the console <a href="https://aws.amazon.com/console/">here</a>.</p><p>Now, we have to choose which region is better for us, we are deciding by the criteria that is the closest to us and have the EC2 services. To select a zone click in the area’s selecting field besides your login username in the top-right corner and select the desired area:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*en2Z4QE9vU8ynakxUlKEwg.png" /></figure><p>As I stated above, we are going to use Amazon EC2 services which stands for <strong>Elastic Computing 2</strong>. In order to access EC2, type EC2 in the search bar and select it from the returned results:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/909/1*y1tctw2tJP1muCLq9MzUBw.png" /></figure><p>You’re going to be taken to the EC2 webpage. Now, we have to get to the Instances’ page. Click in Instances in the left side:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*QTNXr3qqrCKl2wtrLGd2_w.png" /></figure><p>On the Instances’ page we can see our VM instances and their respective status:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FJZfH-asm2zKdHZnu3DDyw.png" /></figure><p>As we want to create a new instance, let’s click on the button lauch instances on the top-right corner:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SGiP-7CZ_uYuc2NWzcU61w.png" /></figure><h3>STEP ONE</h3><p>Now, we’ve got to the VM’s specs. The first thing we want and have to do is to select which AMI(Amazon Machine Image) we want to run.</p><p>What is an AMI? An AMI is a bunch of files which hold instructions and the files to create a brand-new VM with a functional operational system.</p><p>Amazon provides us with lots of images, a few of them are FTI(Free Tier Elegible) that means that we can use them without have to pay for it.</p><p>In the moment that I’m writing this article there are Linux and Windows AMIs available for free. We have just to select which one we want to use and click on the Select button.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7YtU93ttX0rcP_VsojkqYg.png" /></figure><h3>STEP TWO</h3><p>Now that we have selected our AMI, we want to choose how much resources we are going to allocate for our VM. Amazon provides a wide range of resources which can be allocated.</p><p>You can check out the prices in <a href="https://instances.vantage.sh/">this</a> website for the resources’ family member.</p><p><strong>IMPORTANT</strong>: Amazon offers <strong>750 hours/month</strong> for T2 computing power(1 core with 2.5ghz and 1GB RAM.) This amount is enough to run a T2 VM instance for 1 month which has 31 days for 24/7.</p><p>Make sure to select the FTI resources from T2 family like the image below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9RNp4eKPP8melNUTa1xlsw.png" /></figure><p>Now click on Next for configuring instance details:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/606/1*6afo2YD1i_i_-koKdXLiwQ.png" /></figure><h3>STEP THREE</h3><p>The most important part of the configuration details that I want to show you is the bootstrapping option:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*p0MQQS1RnJtFQi9vVlKQzg.png" /></figure><p>Here, we can write a bash code which will run <strong>only </strong>once when the machine is created. You can write whatever you want, you can install packages, upgrade the system, delete files and your imagination is the sky.</p><p>An example of bash code would install python3 on a Debian AMI, something like this:</p><pre>#!/bin/bash<br>apt update &amp; apt-upgrade<br>apt-get install python3</pre><p>When you are ready to go click on the next button in the bottom-right corner:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/497/1*l0_Dphh3qQH7OHrsFStsbg.png" /></figure><h3>STEP FOUR</h3><p>The next section is the storage page, which we are going to choose how much GBs we are allocating for storage data of our VM.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bkPsxn0PLkdjKLG32vNDlA.png" /></figure><p>We can see that the following number marked arrows control:</p><p>1) How much space we are allocating for our VM(Amazon offers 10gb for free).<br> 2) The volume type, Amazon provides us with several data storage types which each one has its own specialty for specific cases. For our VM let’s leave as General Purpose SSD gp2.<br>3) Delete on termination means that if our VM is terminated, our data aren’t going to persist so it’s a good and recommened option for we want to store our data in a separated volume.<br>4) Encryption means if we want to encrypt our storage, in our case it’s not necessary.</p><p>Now that we are good with storage, click on the Next button again:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/465/1*14mUWSfstcwzhPRdDFe4Cg.png" /></figure><h3>STEP FIVE</h3><p>Tags: Tags are as its word says: they are used to give tags for our VM instance. They are useful to identify the VM throughout AWS.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aR_XLR1ci57oGDJtbxvNuA.png" /></figure><p>In order to Tag our VM, click on:<br> 1) Add Tag<br> 2) Write a key <br>3) And finally put one value to it.</p><p>When you are ready with tags click on the Next Button again:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*HS04uc8JhBNaSOrQvcYPBA.png" /></figure><h3>STEP SIX</h3><p>Security Groups are used to control external and internal network access to our VM.</p><p>In order to create a new security group select the option like 1)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9Tis4rqTwTPFm_DaD_O4yQ.png" /></figure><p>And then select Add rule for adding a new rule if you want. By default AWS provides a SSH rule for accessing remotely the VM with SSH. You can delete it if you want but if you delete it you won’t be able to access your VM from outside world.</p><p>A rule have several configuration fields, let’s walk the most important ones:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QKH02Q4x6CW8SxZde3SzMQ.png" /></figure><p>We have:<br>1) The type of the rule: which kind of protocol are we going to allow access from external world? In our case I selected HTTP protocol.<br>2) Port Range means the range of ports which will have be open to the external world for that protocol.<br>3) Source: the source of requests, it can be internal/external specific IP, anywhere or even another security groups.</p><p>That’s it, now click on the Review and Launch:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/398/1*SU3lZXQAamLmWgoXBGEvjA.png" /></figure><h3>STEP SEVEN</h3><p>It’s time to review our setup and launch our VM.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Eoyfs5YO-inc_JgDaFTrCw.png" /></figure><p>Here we can review some points:<br>1) AMI.<br>2) Instance type.<br>3) Security Group and Rules</p><p>If everything is okay, click on the launch button.</p><h3>STEP EIGHT</h3><p>In order to access our VM we must have a private key. You will be prompt to create or select a existent private key as soon as you click on the launch button as depicted below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/704/1*oUiqBiU_8GQgjCQwYmHieA.png" /></figure><p>First, we have to select the option to create a new key pair like depicted in the number one. Second we choose the RSA key pair type which will be the type that we are going to use to connect through SSH. Third type a name for the key. And finally download the new generated key.</p><p>After that, click on the Launch Instance button:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/290/1*0U56IzbJR871L60ndBR8BQ.png" /></figure><p>Now AWS is going to create and launch our instance for us. If everything went fine you are going to see the following screen:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*hEK3khcIrnPMMDKF1bjwLg.png" /></figure><p>Then click on the View Stances button to go to the Instances page again:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/232/1*qul93dUdqIIfaDZPYxzv_g.png" /></figure><p>If everthjing went good you can see the new instance running as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/995/1*De3s3o-GL4dlCxLvhRwunw.png" /></figure><p>To check the status of the brand-new running VM, click on it and it will open the details in the bottom like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*dMPZ_GMAWovyiR9SQchqDA.png" /></figure><p>And that’s it. We have a brand-new running instance running in minutes. We can use its IP address to connect with SSH and do whatever we want.</p><p>Now, if we are not going to use the VM, let’s stop/terminate it.<br>Remember if you stop the instance, the instance won’t consume resources and won’t be online anymore so you won’t be charged if you run out of free hours.</p><p>Right click on the instance which you want to stop and click on Stop Instance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/405/1*pQa2afquKzKMM9Ssn_bQsg.png" /></figure><p>After that, the instance will Stop and it won’t be consuming resources.</p><p>You can also <strong>terminate</strong> an instance, if you terminate an instance and you have selected to delete storage data on termination, the storage data will be lost and the instance will eventually be deleted.</p><h3>Conclusion</h3><p>In this artcile we have learnt how pratical and easy is to create a virtual machine on AWS. That’s a very powerful knowledge nowadays. You can set up a instance in minutes and have powerful resources in our hand.</p><p>I hope you enjoyed it.</p><p>Thanks for reading.</p><p>See you next time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=394330a63ea" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Linked Lists]]></title>
            <link>https://medium.com/@guilhermeluisd/linked-lists-ebef65d01955?source=rss-954879e9e77------2</link>
            <guid isPermaLink="false">https://medium.com/p/ebef65d01955</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Guilherme Luís Dall'Agnol]]></dc:creator>
            <pubDate>Mon, 31 Jan 2022 19:17:12 GMT</pubDate>
            <atom:updated>2022-01-31T19:17:12.407Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>Let’s talk a little about lists. We have already seen <a href="https://medium.com/@guilhermeluisd/arrays-what-are-they-essentially-32fde3b80c90">arrays</a> and how efficient they are. We have also seen that arrays have a fixed-size upon their allocation and they don’t allow insertion beyond its capacity, in other words, it’s impossible to insert a new element in an array which is full.</p><p>Array isn’t the only data structure which can hold a list in sequence. If our application will use more insertion/deletion in certain conditions than look-up we would be better off using a new type of data structures: <strong>Linked Lists</strong>.</p><p>A linked list is a list which every element is <em>linked </em>together by a pointer pointing to the next element. That means that every <strong>node</strong> will have at least two fields: a type holding the information itself and a pointer pointing to the next element. If you have read my article of arrays, by now you probably have realized that the structure which linked lists are organized is different from arrays, for arrays are types in sequence on RAM, on the other hand, linked lists are linked by storing memory addresses and have its size limited by RAM’s capacity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*neSjxFYEVpI57ykMcWqQzg.jpeg" /><figcaption>Source: Google Images</figcaption></figure><p>It’s worth saying that there are two types of linked lists: Single Linked Lists and Double Linked Lists. The only difference between them is that instead of every node holding only a pointer to the next node, it holds a pointer to the previous node.</p><p>That said, let’s dig into how it works.</p><h3>How it works?</h3><p>An implementation of linked list needs creation of two new types/structures.</p><p>The first is the <strong>node</strong>. The node will hold a type which we are going to store data and a pointer to the next node and if it’s a DLL a pointer to the previous node. That’s it. Simple as that.</p><p>The second one is the <strong>list </strong>itself. The list will hold a pointer to the first element, we call it the head, and optionally we can store a integer which will maintain the size of the list.</p><p>Now let’s see what are the time complexity for the four basic operations.</p><h3>Accessing</h3><p>In order to access any element in a linked list, we have to walk through the elements one by one until we reach our desired index. We access the head and we look up if the next pointer is NULL. If it is NULL therefore we have reached the end, otherwise, we keep going until we find our index.</p><p>The time complexity for this operation therefore is: is O(1) * N, O(1 * N) = O(N).</p><h3>Insertion</h3><p>What is the time complexity for inserting an element in a linked list? Well that depends where we are going to insert to.</p><p>For inserting in position N of a linked lists, we have access O(N) + time for inserting is the time for setting the pointer of the N-1 element to the new node O(1), in other words: O(N + 1) = O(N).</p><p>Now, what if we want to insert in the beginning? Now that the magic of Linked Lists shows up. For inserting an element in the beginning we just have to set up a new node that points to the head and adjust the heads for the new node: O(1)!</p><h3>Searching</h3><p>For searching an element we have to do linear search. We first look at the first element, compare to our target value, if we find it then return it otherwise access the next element and so on… that’s O(1) * O(N), O(1 * N) = O(N).</p><h3>Deletion</h3><p>How about deletion? In order to delete any element from the list we have to first search for it and when we find it we delete it. That’s said we have to access the element O(N) and then we delete by setting the pointer of N-1 to N+1 or NULL if the element is the last element of the list. But if we want to do a “pop front” we get constant time O(1)!</p><h3>Conclusion</h3><p>We have seen that the looking-up time for linked lists is O(N), infinitely bigger in comparison against array’s. We have also seen that the insertion time might be as equal as an array if we want to insert it into the middle. But the magic happens when we want to constantly insert/remove elements in the beginning of a list which is O(1).</p><p>Linked Lists are useful, if we are constantly going to insert/delete elements from them, it might be a game changer for your software. It may impact all the performance of your program.</p><p>That’s it for now.</p><p>Thanks for reading.</p><p>See you next time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ebef65d01955" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Arrays, what are they essentially?]]></title>
            <link>https://medium.com/@guilhermeluisd/arrays-what-are-they-essentially-32fde3b80c90?source=rss-954879e9e77------2</link>
            <guid isPermaLink="false">https://medium.com/p/32fde3b80c90</guid>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Guilherme Luís Dall'Agnol]]></dc:creator>
            <pubDate>Sun, 23 Jan 2022 19:46:48 GMT</pubDate>
            <atom:updated>2022-01-23T20:38:51.538Z</atom:updated>
            <content:encoded><![CDATA[<p>Arrays are everywhere, almost every programming language has a type called array, but have you ever wondered what are they? How efficient is an array? What are the time complexity for accessing, searching, inserting and deleting an element of the array?</p><p>In this post, we are going to dig into that.</p><h4>Arrays</h4><p>Arrays are type of <em>data structure</em>. What is a data structure? A data structure is way to organize data together to facilitate the manipulation of those data.</p><p>An array is collection of a type in sequence.</p><p>It is one of the most used data types of all times.</p><p>Every variable type that you declarate has an address in memory with its respective value mapped into the RAM(Random-Access Memory) in your computer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*vzIrGwPXCaZtBZi3" /><figcaption>Source: <a href="https://medium.com/@ethannam/javascripts-memory-model-7c972cd2c239">https://medium.com/@ethannam/javascripts-memory-model-7c972cd2c239</a></figcaption></figure><p>As I said earlier, arrays are a sequence of a type in memory, one after other. Therefore, if we take an element and put in sequence we would have something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/497/0*x8rJxmrzEUk9pEST" /><figcaption>Source: <a href="https://medium.com/@akedalat/how-arrays-allocate-memory-a9bc93c0ad45">https://medium.com/@akedalat/how-arrays-allocate-memory-a9bc93c0ad45</a></figcaption></figure><h3>How efficient is an array data structure?</h3><p>To analyze how efficient a data structure is, we have to think through the time complexity of the operations like: insertion, accessing, deletion, searching and others.</p><p>In this post, I will use C language to facilitates the explanation of arrays.</p><p>Let’s walk in the four basic operations in an array.</p><h4>Accessing</h4><p>What is the time complexity for accessing a member of this data structure?</p><p>Let me first explain to you, how the compiler deals with array’s accessing operation. A computer accesses any address in RAM in constant time, that why is called Random-Access Memory, LOL. And as arrays are sequences of elements in memory and every variable type has an address and a value in memory, if we have the head address of an array and the size of bytes which the array type is, we can access any element by summing the head address plus the size of the array’s type in bytes * index of the element which will be accessed.</p><p>In fact, what the compiler actually does when it sees an expression like: array[5], is to take the array’s head address which is array[0], multiply the size of the array’s type in bytes with the index which is 5 and sum the result with the head address and finally accesses the result address in memory.</p><p>Now let’s see how much time does it take to access an element in an array: 1) To take the head address -&gt; O(1); 2) To multiply the array’s type size in bytes with the index -&gt; O(1); 3) To sum the multiplication result with the head address -&gt; O(1);</p><p>Result: O(1) + O(1) + O(1) = O(1);</p><p>Therefore, the accessing time for array data structure is O(1); Perfect, a gold standard for algorithms.</p><h4>Searching</h4><p>And for searching? What is the time complexity in searching an element in array? As Big O assumes the worst case scenario, in our case: the element which we are looking for isn’t in the array at all!</p><p>There are mainly two types of searching: 1) Linear Search, 2) Binary Search;</p><p>Linear search is when we go through all elements of the array one by one linearly, in time complexity terms: O(n).<br>Meanwhile, binary search is when we look into the middle of the array, then we check if the element is there, if not we half the array in half, select the portion which the element may be in, and repeat the proccess until we find it, in time complexity terms: O(log N). Obs: the array <strong>must</strong> be ordered.</p><p>If we are doing a linear search and as Big O assumes always the worst case scenario, we have to access every element of the array and check if the element is there, it would be O(N) for accessing plus O(N) for checking all the elements of the array. The result is O(N + N), O(2 * N) which is equal to O(N).</p><p>On the other hand, if we are doing a binary search we are accessing log N elements, which is O(1 * log N) complexity time plus log N checking of the element which turns to be also O(1 * log N). The result is O(1 * log N) + O(1 * log N) = O(log N) + O(log N) = O(log N + log N) = O(2 * log N) which turns to be O(log N).</p><p>So we have the time complexity for searching in the two main ways: linear search and binary search which are O(N) and O(log N) respectively.</p><h4>Inserting</h4><p>How about insertion? Well, in order to insert an element in an array we just have to access the index and insert into it but there is a catch: an array has size defined when you declare it and if we reach the capacity, we have to resize the array. Then in order to insert an new element, we have create a new array with a expanded size and copy every single element from the original array into it. The time complexity for allocating a new array with expanded size in memory is the size of the original array O(N) + the expanded size which is a constant. We now have to copy the elements, which is also O(N). So far we Have O(N + expanded size) + O(N) = O(N) + O(N) = O(2 * N) = O(N).</p><h4>Amortized Insertion Time</h4><p>By now, you probably have realized that the time complexity for inserting an element is either O(1) or O(N), it will depend if the size is either full or it has some space. We need a concept to encapsulate both time complexity in only one: <strong>amortized time</strong>.</p><p>A good definition of amortized is:</p><blockquote><em>Amortized time is the way to express the time complexity </em><strong><em>when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time.</em></strong></blockquote><blockquote><em>Source: </em><a href="https://medium.com/@satorusasozaki/amortized-time-in-the-time-complexity-of-an-algorithm-6dd9a5d38045"><em>https://medium.com/@satorusasozaki/amortized-time-in-the-time-complexity-of-an-algorithm-6dd9a5d38045</em></a></blockquote><p>We say that the insertion time complexy for an algorithm which has its size full is O(N) and the <strong>amortized time</strong> for insertion is O(1).</p><h4>Deletion</h4><p>How about deletion? What is the time complexity for deleting an element from the array? As Big O consider only the worst case scenario, we are going to analyze it. The worst case scenario is when our target is the first element. For deleting an element we must first search for it O(N) and then when we find it, we copy every single element for the position I-1 O(N), in Big O terms: O(N) + O(N-1) = O(N) + O(N) = O(2 * N) = O(N).</p><p>Therefore, the time complexity for deleting an element is O(N).</p><h3>Conclusion</h3><p>Arrays are arguebly the most used data structure of all times. We have seen that the time complexity for accessing, searching, inserting and deletion is respectvely O(1), O(N), O(1)/O(N) and O(N).</p><p>Due its time complexity for accessing/modifying, we can take advange of that and use arrays for manipulating easily data in a loop.</p><p>I hope I have broadened your understanding of arrays with this post.</p><p>Thanks for reading.</p><p>See you soon.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=32fde3b80c90" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What is the Big O all about?]]></title>
            <link>https://medium.com/@guilhermeluisd/what-is-the-big-o-all-about-27ad4ba16739?source=rss-954879e9e77------2</link>
            <guid isPermaLink="false">https://medium.com/p/27ad4ba16739</guid>
            <category><![CDATA[big-o]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Guilherme Luís Dall'Agnol]]></dc:creator>
            <pubDate>Sun, 23 Jan 2022 19:43:45 GMT</pubDate>
            <atom:updated>2022-01-23T19:43:45.625Z</atom:updated>
            <content:encoded><![CDATA[<h3>What is Big O all about?</h3><p>Hi there, today I will be writing about all the buzz around the Big O notation.</p><p>If you are somewhat into the programming world you probably have heard about the Big O notation. And you likely have asked yourself WTF is Big O all about? What is the purpose of Big O at all!?</p><p>Well, I intend to answer those questions here and even more.</p><h4>Let’s begin by asking the first question, what the hell is the big O notation?</h4><p>Well, <strong>Big O notation</strong> is a notation which encapsulate a mathematical funcion to measure algorithm performance in the worst case scenario. Big O is inteded to measure HOW WELL an algorithm will perform in an input which approches infinity.</p><p>Notice that I wrote HOW WELL instead of HOW MUCH TIME an algorithm will take to perform a particular task given a certain input. Why? Because to measure how much time an algorithm would take to perform a certain task we would need a lot information which may be even impossible to gather like: input site, CPU power, CPU architecture, the computation power available in the moment of the execution of the algorithm, the language that is performing the algorithm, the compiler and so on…</p><p>Therefore, when computer scientits became crazy facing the problem of having a lot of variables to compute and they started to realize that it wouldn’t be feasible to share the efficiency of an algorithm given those variables, they came up with a concept of assymptotic notation. Assymptotic notation means a language which allows us to analyze the running time of an algorithm given an input which approch infinity.</p><p>So in simple terms, Big O notation is a way to measure how well an algorithm will perform given an input which approaches infinity.</p><h4>What is the purpose of Big O?</h4><p>Suppose you and your friend who is a programmer too are making a competiton to know who makes an algorithm which solves the same problem faster. How would you do it? If the algorithm solves a searching problem and the input array is orderned you could count which algorithm would make less guesses than the other. But how about time? How long will it take to my algorithm perform? and what if the algorithm isn’t even an search problem?</p><p>How can we ignore all those variables which are locally dependent and to know how well our algorithm will perform in any computer in the world? I wouldn’t be fair to count how long is the algorithm running time in my friend’s personal computer which might be faster than mine, right? Yes, you are right.</p><p>So, computer scientists sit and thought about it and they came with a notation which the purpose is to measure how well an algorithm will perform in any given language and in any computer in the world: The Big O notation.</p><h4>Our first notation: Constant Time</h4><p>Now that we know what Big O notation is and what is the purpose of it, we are going to explore how to measure and express in terms of Big O notation.</p><p>In order to perform a task a computer takes time. That’s intuitive.</p><p>We say that a computer takes big O of constant time if the time that an algorithm takes to conclude given an independent size of the input is constant.</p><p>In order to express in a formal way we use the the letter <strong>O</strong> followed by closing parentesis <strong>()</strong> plus the mathematical function <strong>inside</strong> the parentesis, in other terms, to express constant time, we would write: O(1), why 1? and not 2? 3? 4? Because one was chosen to represent constant time.</p><h3>N Notation</h3><p>What would happen if you had an algorithm which takes an array as input of size N and it would perform a constant time of computation in every element of the the array? In terms of Big O notation we would say that it would take O(N) to conclude the algorithm.</p><p>What does it mean? It means that for any given array of size N, it would take (N * constant) time of computation to finish the algorithm.</p><h4>N² Notation</h4><p>Sometimes we have to perform N computations for each element of N in the input size. That’s is the case when you have two fors nested within each other.</p><p>For example:</p><pre>for item1 in array:<br> for item2 in array:<br>  do(something, with, item1, and, item2)</pre><p>That would give us O(N²)!</p><p>Now, at this point if you have a basic understanding of mathematical functions you will intuitively understand that N &lt; N². Therefore we can conclude that the running time for O(N) is LESS than than O(N²).</p><h3>Other notations</h3><p>We have seen three notations so far, but there are others.</p><p>Some of them are: √N ,log N, n log n, N², N³, N!(factorial), 2^N and so on…</p><h3>How to calculate the Big O of an algorithm</h3><p>The first step to calculate the Big O of an algorithm is to calculate how many computation an algorithm will take to conclude.</p><p>We can begin by a simple algorithm which returns the first element of the input array:</p><pre>def display_first_element(input):<br>    return input[0]</pre><p>It doesn’t matter what the size of the input IS, the amount of work that the algorithm will have to do is just to look up the first element(constat time for <strong>arrays</strong>) and return it. We would say that this algorithm takes O(1 + 1) time to perform its task. Why? Because if we are going to be rigorous, we would have to calculate the amount of time taken for the array lookup(constant time O(1)) plus the amount of time for returning the result which turns out to be O(1) too. Therefore if we sum both of them we get O(1 + 1).</p><h4>Summing constants</h4><p>Let’s go back to the previous example where we take an input array and return the first element of the array. It says that its running time is O(1 + 1). In other words it’s the sum of the running time of getting the first element(which is constant) and the the sum of returning the element. Both operations are O(1) and as I said earlier O(1) is constant time of work. But how much time is it? The fact is that we don’t know because we don’t know those variables which are unfeasable to calculate. It can be 1ms 10ms 1sec, we don’t know. What we know is that it is <em>constant</em> time. It doesn’t matter the size of the array, it will take a CONSTANT time to finish.</p><p>Therefore, for Big O, there is no difference between expressing the sum of Big(1 + 1) and Big(1), because the sum of two cosntants time results in a constant time itself.</p><p>Because of that, we sum the constants time and we represent with the notation of constant time which is O(1).</p><h4>Dropping constants</h4><p>Now let’s suppose that we have an algorithm which is O(N) which is it will go through all the items of the array in the worst case scenario.</p><p>The following algorithm takes an array and a target as input, try to find the target in the array and finally it returns the index of the element in the array:</p><pre>def n_algorithm(input, target):<br>    index = 0<br>    for item in input:<br>         if item == target:<br>             return index<br>         index += 1<br>    return None</pre><p>If we were to be rigorous, we would begin to calculate the running time of index = 0 which is constant time O(1), then we would go to the loop which would take O( 3 * N), why? Because there are three operations which are done by iteration of N: 1) Getting a value from input, 2) Comparing to target and finally 3) Incrementing the index. All of them takes constant time to compute but they are done N times. So we have O(3 * N) time of work. And for last we have the returning statement which either be executed within the loop or outside the loop one time = O(1). Therefore we have O(1 + 1 + 3 * N).</p><p>Here is a fact, Big O doesn’t care about constants. It only cares about the growth rate of a function. Then for Big O notation, O(3 * N) is the same as O(N).</p><p>Knowing that we have O(1 + N) which is O(N) the explanation of this comes in the next topic which is…</p><h4>Dropping the non-dominant terms</h4><p>Suppose we have an algorithm which performs a linear search and then performs a O(N²) computation. As follows:</p><pre>def f(array):<br>    for item in array:<br>        do(something)</pre><pre>for item1 in array:    <br>    for item2 in array:<br>        do(something, with, item1, and, item2)</pre><p>What would be the time complexity of this algorithm? O(N)? O(N²) or O(N + N²)? If you said O(N²) then you are damn right. Why? Because when we are computing the Big O, we drop the non-dominant terms. What does it mean? It means that we consider only the terms that dominates the growth rate. No matter how large N is, N² will always, I mean ALWAYS be significantly larger than N. In light of that we consider only the terms which are dominant, in our case N².</p><h3>Conclusion</h3><p>Big O notation is a quite powerful and useful notation. It allows us to analyze fairly the running time of an algorithm in any computer in the world, in any given language with any compiler.</p><p>It allows us to compare algorithms and decide which one will performs faster.</p><p>That’s it for now.</p><p>I hope you enjoyed it.</p><p>Thanks for reading.</p><p>Did you like it? Here is more power for you:</p><p><a href="https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation">https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation</a></p><p><a href="https://www.youtube.com/watch?v=V6mKVRU1evU">https://www.youtube.com/watch?v=V6mKVRU1evU</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=27ad4ba16739" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>