Hey, guess what, today is #TheoryThursday 🧐!

A silly excuse I just invented to share with you random bits of theory from some dark corner of Computer Science and make it as beginner-friendly as possible πŸ‘‡
Today I want to talk about *Algorithmic Complexity *.

To get started, take a look at the following code. How long do you think it will take to run it?

Let's make that question more precise. How long do you think it will take to run it in the worst-case scenario?
We can see that the code will run slower if:

πŸ‘‰ your computer is older;
πŸ‘‰ the array is longer; or
πŸ‘‰ x happens to be further to back, or not present at all.

Can we turn these insights into an actual formula? We will have to get rid of ambiguous stuff like "old computers".
1️⃣ First, let's consider an abstract computer in which all "atomic" operations take exactly 1 unit of time.

πŸ€” Defining exactly what is an "atomic" operation is far from trivial. For now, assume it's things like arithmetic operations, indexing, invocation.
2️⃣ Second, we'll count the number of operations *with respect to* the size of an arbitrary array.

We will say something like "this will cost 2 units of time for each element of the array".
3️⃣ Finally, we will consider the worst-case scenario.

So we assume, in this example, that the element x is not in the array. More generally, we will always think about the maximum number of operations that could potentially happen.
With these ideas in mind, we are ready to define the *Algorithm Complexity* of this algorithm.

Let's count how many operations are performed in each step, assuming our array has length N:
Depending on how detailed you want to be counting, you could say we have something like πŸ”₯3*N+1πŸ”₯ operations in the ultimate worst-case scenario.

❓ Now, why do we care about this?

The reason is that we can now compare different algorithms.
For example, if your implementation takes πŸ”₯5*N+3πŸ”₯, then it is worse, right?

Well, it's not 😝

Here's the deal: we have been assuming that all "atomic" operations are equally costly, but this is not true...
Hence, it makes no sense to compare my implementation with your implementation by looking at those tiny differences. My 5 * N could be faster than your 3 * N if my "atomic" operations are simpler.

πŸ’‘ We want a complexity measure that smooths away all implementation details.
To achieve this, we will take away everything unimportant when N becomes very large. We will consider that:

πŸ‘‰ N+a and N+b are the same;
πŸ‘‰ a*N and b*N are the same;

... for any finite values a and b.
πŸ”‘ And instead of saying 3*N+4, we will say the asymptotic algorithmic complexity is O(N).

This is called big-O notation.

πŸ’‘ We call this *linear complexity* because the number of operations grows linearly *with respect to* the size of the array.
🧐 Formally, it means that your function's cost is something that is bounded by a linear function.

πŸ’‘ Intuitively, what this means is that in the long run, small differences like specific operations matter less than the capacity your algorithm has to *scale* with more data.
The reason is simple, an algorithm with a lower asymptotic complexity will eventually win. Take for example binary search.

en.wikipedia.org/wiki/Binary_se…

It takes a bit of thinking, but we can prove the asymptotic notation to be O(log N).
Binary search is doing much more work in each iteration than linear search. It could be 20 * log N vs 3 * N. Hence, with very small arrays, linear search could be better.

πŸ”‘ But there is always a value of N after which binary search will win, and in any hardware.
❀️ And that's it. We have just arrived at the intuitive notion of asymptotic complexity!

Calculating it can be daunting for some non-trivial algorithms, but here are some tips for estimating it:
1️⃣ Every nested for loop from beginning to end usually means another exponent.

For example, two nested loops usually mean O(N^2), three nested loops, O(N^3), and four nested loops means you really need to take a break and, afterwards, please refactor that code.
2️⃣ An invocation to function F inside a loop means you have to multiply N times the complexity of F.

For example, if we call binary search for each element of the array, the resulting algorithm is O(N log N)
3️⃣ In recursive methods, if you split at the middle and recurse down only one branch, that's O(log N). If you recurse down both branches, you usually have O(N log N).

These are special cases of a more general rule for recursive methods:

en.wikipedia.org/wiki/Master_th…
Finally, we have just scratched the surface in this thread. Algorithmic complexity is a fascinating topic that touches all fields in Computer Science.

The most important problem in all of CS comes from here, the infamous πŸ”₯P vs NPπŸ”₯.

But that's a story for another Thursday πŸ˜‰.
πŸ—¨οΈ If you like this idea, then get into the conversation! Steal this #TheoryThursday hashtag an tell me about your favourite piece of dark magic.

πŸ”” Just @ me and I'll make sure to weigh in.

πŸ—’οΈ Here is the full thread source:
github.com/apiad/apiad.gi…

β€’ β€’ β€’

Missing some Tweet in this thread? You can try to force a refresh
γ€€

Keep Current with Alejandro Piad Morffis

Alejandro Piad Morffis Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @AlejandroPiad

3 Feb
There seems to be a recent surge in the "HTML is/isn't a programming language" discussion.

While there are a lot of honest misconceptions and also outright bullshit, I still think if we allow for some nuance there is a meaningful discussion to have about it.

My two cents πŸ‘‡
First, to be bluntly clear, if a person is using this argument to make a judgment of character, to imply that someone is lesser because of their knowledge (or lack of) about HTML or other skills of any nature, then that person is an asshole.

With that out the way...
Why is this discussion meaningful at all?

If you are newcomer to the dev world and you have some misconceptions about it, you can find yourself getting into compromises you're not yet ready for, or letting go options you could take.
Read 10 tweets
2 Feb
This is a Twitter series on #FoundationsOfML. Today, I want to talk about another fundamental question:

❓ What makes a metric useful for Machine Learning?

Let's take a look at some common evaluation metrics and their most important caveats... πŸ‘‡πŸ§΅
Remember our purpose is to find some optimal program P for solving a task T, by maximizing a performance metric M using some experience E.

We've already discussed different modeling paradigms and different types of experiences.

πŸ‘‰ But arguably, the most difficult design decision in any ML process is which evaluation metric(s) to use.
Read 25 tweets
31 Jan
One of the very interesting questions that really got me thinking yesterday (they all did to an important degree) was from @Jeande_d regarding how to balance between learning foundational/transferable skills vs focusing on specific tools.
@Jeande_d My reasoning was that one should try hard not to learn too much of a tool, because any tool will eventually disappear. But tools are crucial to be productive, so one should still learn enough to really take advantage of the unique features of that tool.
@Jeande_d One way I think you can try to hit that sweet spot is practice some sort of dropout regularization on your common tool set.

In every new project, substitute one of your usual tools for some convenient alternative. It will make you a bit less productive, to be sure...
Read 5 tweets
13 Jan
This is a Twitter series on #FoundationsOfML.

❓ Today, I want to start discussing the different types of Machine Learning flavors we can find.

This is a very high-level overview. In later threads, we'll dive deeper into each paradigm... πŸ‘‡πŸ§΅
Last time we talked about how Machine Learning works.

Basically, it's about having some source of experience E for solving a given task T, that allows us to find a program P which is (hopefully) optimal w.r.t. some metric M.

According to the nature of that experience, we can define different formulations, or flavors, of the learning process.

A useful distinction is whether we have an explicit goal or desired output, which gives rise to the definitions of 1️⃣ Supervised and 2️⃣ Unsupervised Learning πŸ‘‡
Read 18 tweets
12 Jan
A big problem with social and political sciences is that they *look* so intuitive and approachable that literally everyone has an opinion.

If I say "this is how quantum entanglement works" almost no one will dare to reply.

But if I say "this is how content moderation works"...
And the thing is, there is huge amount of actual, solid science on almost any socially relevant topic, and most of us are as uninformed in that as we are on any dark corner of particle physics.

We just believe we can have an opinion, because the topic seems less objective.
So we are paying a huge disrespect to social scientists, who have to deal every day with the false notion that what they have been researching for years is something that anyone, thinking for maybe five minutes, can weigh in. This is of course nonsense.
Read 5 tweets
12 Jan
I'm starting a Twitter series on #FoundationsOfML. Today, I want to answer this simple question.

❓ What is Machine Learning?

This is my preferred way of explaining it... πŸ‘‡πŸ§΅
Machine Learning is a computational approach to problem-solving with four key ingredients:

1️⃣ A task to solve T
2️⃣ A performance metric M
3️⃣ A computer program P
4️⃣ A source of experience E
You have a Machine Learning solution when:

πŸ”‘ The performance of program P at task T, as measured by M, improves with access to the experience E.

That's it.

Now let's unpack it with a simple example πŸ‘‡
Read 23 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!

Follow Us on Twitter!