DEV Community: Paweł

The Big O notation - O(n)

Paweł — Sun, 29 Sep 2019 18:20:17 +0000

1. Why I've chosen to write this article?

I have found the Big O notation could be scary for many beginner programmers (including me some time ago). The subject is really simple and it is worth to dedicate few minutes to read this article.

2. What is this notation and why is it important?

The Big O notation describes complexity of an algorithm. Basically it tells you how fast the algorithm is. Simple enough. The O in name stands for 'order of' or 'Ordnung'. It comes from the German number theoretician Edmund Landau and later it was adopted to Computer Science world.

As a programmer you use or would use many algorithms written by other people. Consider that you would use another person's solution (i.e. from stackoverflow). Then you would love to know how fast the algorithm is.

Take a look at the first trivial example. You have a sheet of paper and you have to divide it into 16 parts.

How would you do that? The very first thought is that you can take a pen and write 16 squares one by one.

If you think about it as an algorithm you will realize that this is not an optimal solution. You would have to make 16 steps to finish the task.

Someone else could say that you can fold the sheet 4 times and you also would have the sheet divided in 16 squares.

Now you have 2 solutions, one better that another and you would like to describe them. With Big O notation it is really simple.

3. What Big-O notation really describes?

Imagine that you are a librarian and you have to find Mr. Smith's library card. What would you do if in a drawer there would be 1000 unordered cards and somewhere inside the Smith's card is hidden. First thought is that you would have to check every card one by one until you'll find the right card. Maybe the first one is the card that you are looking for, which is good, but maybe it is the last one... You would have to check 1000 then. It is the worst scenario and Big-O notation describes exactly this - the worst scenario of an algorithm.

If n in this notation is a number of operations (in the worst case) we can say that our algorithm has a complexity of O(1000) which in general is just O(n) because the number 1000 is a variable.

How would we describe an example with a sheet of paper?

O(n) - scenario with a pen and drawing squares one by one.
O(log2(n)) - scenario with folding the sheet of paper.

4. The most common complexities.

Below you have the most common examples of the Big-O notation shown in a graph. I decided to use this graph because it perfectly shows why i.e O(n) is better than O(n!).


Source: lukasmestan.com

The graph is simple to read. If there are more elements (n) the algorithm is obligated to make more operations. Let's compare the best case O(log2(n)) and the mentioned O(n). Binary search is a perfect example of O(log2(n)) complexity. We can see in the plot above that it is almost constant even if we multiply the number of elements in algorithm. See the example below where we are looking for a number 37 using binary search compared with sequential search.


Source: mathwarehouse

The situation with binary search (O(log2(n))) is almost perfect because no matter how many elements we would have, the number of made operations would not grow so much. Believe me or not but if we would have one milion elements in above example in binary search we would have to make at most 20 (O(log2(1 000 000)) = ~20) operations to find a number we are looking for. AMAZING!

With this knowledge you can chose the best algorithm.

You can say that there is no chance that you decide to use O(n!) algorithm.

Well, there is a chance. There is a problem called Travelling Salesman Problem. It answered the question ,,Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?". This can be solved only by the algorithm with O(n!) complexity.

Despite of that you always would like to use algorithm of O(log2(n)) complexity, but sometimes it is not possible because some problems required more complicated solutions.

This article was inspired by a book ,,Grokking Algorithms" written by Aditya Y. Bhargava.

What are Single Page Applications(SPA)?

Paweł — Sun, 15 Sep 2019 09:18:42 +0000

Have you ever heard about some of JavaScript frameworks, such as AngularJS, React or Vue.js? Maybe you would like to learn it but you don't know in general why there are so popular? All of them have adopted SPA principles. What is SPA? Let's start from the beginning...

The 'old' websites

Let's assume that you have been developing the websites in the 'old' way. The end user opens it in the browser and navigate through it.

Aside graphical interface the whole page was downloaded from the server. Every click resulted in sending a bunch of files by the server. Moreover if the user has bad internet connection this exchange might cause seconds to load the page! This is how it have been working behind the scenes.


Source: microsoft

Wouldn't it be nice to involve the server only once to load the page and navigate through it ? This is where SPA comes in.

What actually is SPA?

Wikipedia provides rather clear definition but let's take a closer look

,,A single-page application (SPA) is a web application or web site that interacts with the user by dynamically rewriting the current page rather than loading entire new pages from a server."

Let's dive deeper.

SPA loads all the bundled content for the first time when you make a request by typing i.e. www.myAwesomeSPAWebsite.com in the browser.


Source: microsoft

You can see that after the initial response from the server later on it would send the JSON data. Most of the requests in the app are moved to the client side. Server is mostly responsible for authentication and connecting with database.

In popular SPA frameworks such as React, Vue, Angular, code of the website is split in components. In general when you navigate through the page, other components are rendered replacing the content instead of download it from the server and reloading the whole page.


Source: giphy

SPA pros

Using the website is faster - Because everything is loaded by the first time the client can change the content on the page instantly. In other words our app works like the desktop application because it doesn't need to communicate with the server again to properly display the page.
Decreases the server load - SPA works different with the server at the communication level than the traditional page. To understand this better we can compare this process with building a house. Imagine that you(client) would have to carry bricks(data) one by one wasting your time(like in traditional websites) or you can just use the wheelbarrow(all of the data) and load all of them at once(using SPA). Now you have to transport them only once at the beginning. From now on you do not care that a bricklayer sends you to bring some bricks again. You (the server) can rest.
User experience (UX) - UX refers to any interaction a user has with a product or a service. The fact that you don't have to wait till the page reloads, gives you more pleasure of using it.
Less amount of transmitted data - I have mentioned that all the data is loaded at at once at the beginning. Moreover there are mechanisms that allows us to define which data should be loaded on the first request and which can be load later. It also increases the UX of the app.
Modern solutions - Thanks to use modern solutions the code of an app can be more minified. You are also able to use microservices. This gives you a possibility to divide your app into services that provide an API.

SPA cons

Developers pay more - SPA can be simply written in HTML, JS and CSS but sooner or later you will realize that you need to learn i.e. Webpack, Express, React/Vue/Angular and other accompanying solutions. This can be frustrating at the beginning but it is worth to learn them.
SEO - Search engine crawlers like Googlebot and Bingbot are designed to index web pages through a process known as spidering or crawling, where they download the page’s HTML file(s). That's why it is easier to index and rank a static HTML-based web page. When it comes to indexing JavaScript-based SPAs, things get a little complicated. You have to make more effort to take care about the SEO.

Summary

Should you use SPA for your future projects?
Well, as always you should consider every pros and cons to choose the best option. Maybe it is not worth to develop SPA, maybe the overall cost would be too much. There can be more subjective pros and cons depending on the developer preferences. However it is worth to keep track this rapidly developing SPA world.