Timeline for Which approach of mine for an algorithm upper bound is correct?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 15, 2022 at 23:22 | comment | added | John L. | @fastttt You are welcome! | |
| Apr 15, 2022 at 23:17 | comment | added | 0Interest | Thank you so much! :) | |
| Apr 15, 2022 at 23:17 | vote | accept | 0Interest | ||
| Apr 9, 2022 at 14:12 | history | edited | John L. | CC BY-SA 4.0 |
Stronger conclusion. More math.
|
| Apr 7, 2022 at 5:07 | comment | added | John L. | @fastttt, please come here for a chat. | |
| Apr 7, 2022 at 4:50 | comment | added | 0Interest |
In the first approach, i took the fact that if we find the number in the list, we add it, and thus if in the first iteration the in operator took $O(N)$ the second one would take $O(N+1)$ and so on.. and the maths get $O(N^2 \lg(N))$. The second approach says this: if we find the number, it is already in the first $N$ elements, and if it is not there, we wont add it and it would take $O(N)$. thus we can say in this situation the in operator takes $O(N)$ (starting value of $|S|$) and not the "updating" size of $S$. So which approach is more correct in your opinion?
|
|
| Apr 6, 2022 at 21:00 | history | edited | John L. | CC BY-SA 4.0 |
Minor correction.
|
| Apr 6, 2022 at 20:24 | history | answered | John L. | CC BY-SA 4.0 |