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

belgoros
Following the steps described in Chapter 6 of the book, I’m stuck with running the migration as described on page 84: bundle exec sequel...
New
johnp
Hi Brian, Looks like the api for tinydb has changed a little. Noticed while working on chapter 7 that the .purge() call to the db throws...
New
edruder
I thought that there might be interest in using the book with Rails 6.1 and Ruby 2.7.2. I’ll note what I needed to do differently here. ...
New
Mmm
Hi, build fails on: bracket-lib = “~0.8.1” when running on Mac Mini M1 Rust version 1.5.0: Compiling winit v0.22.2 error[E0308]: mi...
New
AleksandrKudashkin
On the page xv there is an instruction to run bin/setup from the main folder. I downloaded the source code today (12/03/21) and can’t see...
New
fynn
This is as much a suggestion as a question, as a note for others. Locally the SGP30 wasn’t available, so I ordered a SGP40. On page 53, ...
New
Charles
In general, the book isn’t yet updated for Phoenix version 1.6. On page 18 of the book, the authors indicate that an auto generated of ro...
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
andreheijstek
After running /bin/setup, the first error was: The foreman' command exists in these Ruby versions: That was easy to fix: gem install fore...
New
gorkaio
root_layout: {PentoWeb.LayoutView, :root}, This results in the following following error: no “root” html template defined for PentoWeb...
New

Other popular topics Top

wolf4earth
@AstonJ prompted me to open this topic after I mentioned in the lockdown thread how I started to do a lot more for my fitness. https://f...
New
dasdom
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
Rainer
My first contact with Erlang was about 2 years ago when I used RabbitMQ, which is written in Erlang, for my job. This made me curious and...
New
AstonJ
Seems like a lot of people caught it - just wondered whether any of you did? As far as I know I didn’t, but it wouldn’t surprise me if I...
New
AstonJ
Continuing the discussion from Thinking about learning Crystal, let’s discuss - I was wondering which languages don’t GC - maybe we can c...
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
AstonJ
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol: bre...
New
New
New
PragmaticBookshelf
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New

Sub Categories: