Timeline for Binary Search Implementation Using Slicing
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 19, 2021 at 20:04 | comment | added | ten do | Thanks for the detailed explanation | |
| Feb 19, 2021 at 20:02 | comment | added | Rustam Garayev | when implementing recursive solution, space complexity can be O(log(n)) depending on how memory is used in recursive call stacks and it depends on the language of choice. That is why it is recommended to use iterative solution over recursive one. But usually we say it is O(1) since we are not storing anything in variables or something. | |
| Feb 19, 2021 at 19:55 | comment | added | ten do | got it thanks sorry my bad for time complexity for len of list i was taking it as O(k) instead of O(1) and with your implementation it will reduce the space complexity from O(n) to O(1)? | |
| Feb 19, 2021 at 19:18 | comment | added | Rustam Garayev | @tendo Only thing is getting affected is space complexity since you are creating extra space in each recursive function call. Time complexity would remain unchanged. | |
| Feb 19, 2021 at 19:03 | comment | added | ten do | had a query. For the implementation given in the question would the time complexity be O(klogn) where k is the size of the slice or it will remain unchanged? | |
| Feb 17, 2021 at 20:39 | history | edited | Rustam Garayev | CC BY-SA 4.0 |
added 1169 characters in body
|
| Feb 17, 2021 at 20:39 | comment | added | ten do | Thank you. It helps | |
| Feb 17, 2021 at 20:38 | vote | accept | ten do | ||
| Feb 17, 2021 at 20:36 | history | edited | Rustam Garayev | CC BY-SA 4.0 |
added 1169 characters in body
|
| Feb 17, 2021 at 20:12 | comment | added | ten do | Yes because the implementation has to be modified slightly. | |
| Feb 17, 2021 at 19:50 | comment | added | Rustam Garayev | So you want recursive solution with a better complexity? | |
| Feb 17, 2021 at 19:44 | comment | added | ten do | Thanks but for the implementation mentioned in the question how can we modify it slightly so that complexity is improved? | |
| Feb 17, 2021 at 19:40 | history | answered | Rustam Garayev | CC BY-SA 4.0 |