A Common-Sense Guide to Data Structures and Algorithms, Second Edition: wrong Big(O) (Page93)

Community PragProg Customers
,
1

In chapter 6,
Screenshot 2021-07-10 212441
Page 93/438.
"But now, in the best-case scenario, where the two arrays are identical, we only have to perform N comparisons. "

For 2 identical arrays [1,2,3,…, 10]. I think it would take N^2 / 2 steps for the best-case scenario. 1 in 1st array compare to 1 in 2nd array takes 1 step, 2 in 1st arr compare to 1 and 2 in 2nd array take 2 steps. so it is 1 + 2 + 3 +… + 10 = 55 ~ 10^2 /2.

1 Like
2

Thanks for submitting this! I believe you are correct, and this will be fixed in an upcoming version.

Thanks,
Jay