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

cro
I am working on the “Your Turn” for chapter one and building out the restart button talked about on page 27. It recommends looking into ...
New
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
curtosis
Running mix deps.get in the sensor_hub directory fails with the following error: ** (Mix) No SSH public keys found in ~/.ssh. An ssh aut...
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
jskubick
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint. As entered, the SwitchCompat changes color to hol...
New
akraut
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
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
mcpierce
@mfazio23 I’ve applied the changes from Chapter 5 of the book and everything builds correctly and runs. But, when I try to start a game,...
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
roadbike
From page 13: On Python 3.7, you can install the libraries with pip by running these commands inside a Python venv using Visual Studio ...
New

Other popular topics Top

Devtalk
Reading something? Working on something? Planning something? Changing jobs even!? If you’re up for sharing, please let us know what you’...
1033 17470 383
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
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
New
Margaret
Hello content creators! Happy new year. What tech topics do you think will be the focus of 2021? My vote for one topic is ethics in tech...
New
Rainer
Not sure if following fits exactly this thread, or if we should have a hobby thread… For many years I’m designing and building model air...
New
gagan7995
API 4 Path: /user/following/ Method: GET Description: Returns the list of all names of people whom the user follows Response [ { ...
New
AstonJ
Saw this on TikTok of all places! :lol: Anyone heard of them before? Lite:
New
New
New
AstonJ
This is cool! DEEPSEEK-V3 ON M4 MAC: BLAZING FAST INFERENCE ON APPLE SILICON We just witnessed something incredible: the largest open-s...
New

Sub Categories: