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
lirux
Hi Jamis, I think there’s an issue with a test on chapter 6. I own the ebook, version P1.0 Feb. 2019. This test doesn’t pass for me: ...
New
joepstender
The generated iex result below should list products instead of product for the metadata. (page 67) iex&gt; product = %Product{} %Pento....
New
alanq
This isn’t directly about the book contents so maybe not the right forum…but in some of the code apps (e.g. turbo/06) it sends a TURBO_ST...
New
brian-m-ops
#book-python-testing-with-pytest-second-edition Hi. Thanks for writing the book. I am just learning so this might just of been an issue ...
New
jskubick
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint. As entered, the SwitchCompat changes color to hol...
New
Henrai
Hi, I’m working on the Chapter 8 of the book. After I add add the point_offset, I’m still able to see acne: In the image above, I re...
New
davetron5000
Hello faithful readers! If you have tried to follow along in the book, you are asked to start up the dev environment via dx/build and ar...
New
dachristenson
I just bought this book to learn about Android development, and I’m already running into a major issue in Ch. 1, p. 20: “Update activity...
New
dachristenson
@mfazio23 Android Studio will not accept anything I do when trying to use the Transformations class, as described on pp. 140-141. Googl...
New

Other popular topics Top

New
AstonJ
We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
New
AstonJ
I have seen the keycaps I want - they are due for a group-buy this week but won’t be delivered until October next year!!! :rofl: The Ser...
New
Exadra37
Oh just spent so much time on this to discover now that RancherOS is in end of life but Rancher is refusing to mark the Github repo as su...
New
rustkas
Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
New
Help
I am trying to crate a game for the Nintendo switch, I wanted to use Java as I am comfortable with that programming language. Can you use...
New
New
PragmaticBookshelf
Author Spotlight: Peter Ullrich @PJUllrich Data is at the core of every business, but it is useless if nobody can access and analyze ...
New
First poster: bot
zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig. General-purpose programming language and toolchain for maintaini...
New
PragmaticBookshelf
Develop, deploy, and debug BEAM applications using BEAMOps: a new paradigm that focuses on scalability, fault tolerance, and owning each ...
New

Sub Categories: