Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Clarification Required on find() Access Time in Exercises 1.5.4 and 1.5.3 #307

Open
xzy2022 opened this issue Mar 24, 2024 · 1 comment
Open

Comments

@xzy2022
Copy link

xzy2022 commented Mar 24, 2024

In Exercise 1.5.4, it's noted that executing the find() function on a node at depth i results in i+1 accesses to the id[] array. This was particularly apparent when analyzing the example with the second pair input, 3 8, where executing find(3) resulted in two accesses since the parent of node 3 is node 4. However, there seems to be a contrasting scenario in Exercise 1.5.3, where the find() function on a node at the same depth i necessitates 2i+1 accesses.

This variance has caused some uncertainty, and I'm inclined to believe the formula from Exercise 1.5.3 might be the correct interpretation. Could there be a detail I've missed that explains this inconsistency, or is there a definitive correct approach among the two? I am seeking further clarification to comprehend the intended behavior of the find() function within these contexts

@reneargento
Copy link
Owner

You are correct, in the find() method we should count 2i + 1 accesses on depth i.
I updated exercise 1.5.4 to fix that: 62da660
Thanks for reporting this issue and for the contribution.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants