- #1

r0bHadz

- 194

- 17

**Problem Statement:**I've attached a picture of his notes. For a sorted array, to update it he put: O(logn)+O(1)

**Relevant Equations:**O(n) + O(logn) = O(n)

I don't see how it can be O(logn)+O(1) and not O(logn)+O(n) in the worst case

After you find the index that needs updating, and you actually change the value (which is O(1),) since it is a sorted array, let's assume that the last element of that has a value gets updated and now it's updated value belongs to the very front of the array. We would have to then move (n-1) elements and make one assignment. How is that not O(n)?

**[Moderator's note: Moved from a homework forum.]**

#### Attachments

Last edited by a moderator: