DEV Community

Cover image for How to reduce the time complexity of nested loops

How to reduce the time complexity of nested loops

Leandro Proença on December 04, 2021

In this post I'll demonstrate a way to understand, analyse and reduce the time complexity on algorithms, specially on nested loops. The examples w...
Read full post
Collapse
 
hugaomarques profile image
Hugo Marques •

Once, at a job, I did this exact solution. We had a code to compare if something was in the loop. We had process an order of 31_000 records. Therefore, nested loop of 31_000 x 31_000 (don't ask me why, it was like 20 years ago :D).

I used the approach described here to avoid the nested loop and used the map instead. Voi la, instant win!

Collapse
 
krunalpatel3 profile image
Krunal Patel •

nice explanation thanks.

Collapse
 
djangotricks profile image
Aidas Bendoraitis •

Thanks! That's one of the best descriptions of O() notation I've ever read.

However, can you please elaborate on the following example?

users_idx = {}

for user in users
  users_idx[user[:group_id]] = ...
end

for group in groups
  user_information = users_idx[group[:id]]
  # do something with group AND user information
end
Enter fullscreen mode Exit fullscreen mode

What is the relation of users and groups in your example? Many-to-many or many-to-one?

What is saved in the index? All users who belong to a particular group? Or a single user who belongs to a particular group?

Collapse
 
leandronsp profile image
Leandro Proença •

Thanks! The relation between users and groups here are very simple. Please check out the Gist:

gist.github.com/leandronsp/70f9eff...

Let me know if needed more explanation.

Cheers!

Collapse
 
beingnile profile image
Nile •

Just recently learnt Big O and this article gives a good perspective, Thank you!!