andreas-yin

andreas-yin

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Time Complexity for Intersection Function (page 93)

@jaywengrow

I have noticed a mistake regarding the best-case scenario time complexity for the intersection function described on p. 92/93:

function intersection(firstArray, secondArray) {
let result = [];
for (let i = 0; i < firstArray.length; i++) {
for (let j = 0; j < secondArray.length; j++) {
if (firstArray[i] === secondArray[j]) {
result.push(firstArray[i]);
break;
}
}
}
return result;
}

In the case of a best-case scenario, i.e. with two arrays being identical, the parapgrah says we’d only have to perform N comparisons.

But when you have two identical arrays, e.g. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], the inner loop would still have to start at index 0 for every value of the outer loop. So when the outer loop reaches the number 10, the inner loop would still have to compare this number 10 with 1, 2, 3, 4, 5, 6, 7, 8, 9 before it gets to the number 10. So I figured the number of comparisons would be calculated as follows:
1 + 2 + 3 + … + (N-1) comparisons, which is approximately N² / 2 comparisons

Therefore, the time complexity should be O(N² / 2) instead of O(N).

Where Next?

Popular Pragmatic Bookshelf topics Top

ianwillie
Hello Brian, I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New
adamwoolhether
When trying to generate the protobuf .go file, I receive this error: Unknown flag: --go_opt libprotoc 3.12.3 MacOS 11.3.1 Googling ...
New
jskubick
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
New
digitalbias
Title: Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana on (page 64) If you follow the defau...
New
brunogirin
When installing Cards as an editable package, I get the following error: ERROR: File “setup.py” not found. Directory cannot be installe...
New
kolossal
Hi, I need some help, I’m new to rust and was learning through your book. but I got stuck at the last stage of distribution. Whenever I t...
New
mert
AWDWR 7, page 152, page 153: Hello everyone, I’m a little bit lost on the hotwire part. I didn’t fully understand it. On page 152 @rub...
New
jwandekoken
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: d...
New
ggerico
I got this error when executing the plot files on macOS Ventura 13.0.1 with Python 3.10.8 and matplotlib 3.6.1: programming_ML/code/03_...
New
redconfetti
Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
New

Other popular topics Top

malloryerik
Any thoughts on Svelte? Svelte is a radical new approach to building user interfaces. Whereas traditional frameworks like React and Vue...
New
Exadra37
I am thinking in building or buy a desktop computer for programing, both professionally and on my free time, and my choice of OS is Linux...
New
PragmaticBookshelf
Design and develop sophisticated 2D games that are as much fun to make as they are to play. From particle effects and pathfinding to soci...
New
Exadra37
I am asking for any distro that only has the bare-bones to be able to get a shell in the server and then just install the packages as we ...
New
mafinar
Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New
AstonJ
Saw this on TikTok of all places! :lol: Anyone heard of them before? Lite:
New
AstonJ
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
New
New

Sub Categories: