0

Can I subtract an integral value from all elements of an array in constant time?
For example:
Given array: 1 2 3 4

Expected array:0 1 2 3
I want this result in O(1) time complexity.Is this possible?
If yes,How can I achieve the same?


P.S.:The expression a[100]={0}; initializes all cells of array to zero without using the for loop.I am looking for similar expression

user6889367
  • 123
  • 2
  • 7
  • What are the inputs? Is there a limit on the size of the array? What about the size of the numbers being added/subtracted? Big-O means nothing without first explaining what is growing asymptotically. – Andrew Nov 11 '16 at 02:57

2 Answers2

2

You can't change n elements in memory in less than O(n) time, but you can change what that memory represents. If you were to create a custom array class you can include an offset member. When an array element is read you add the offset on demand. When an element is added, you subtract the current offset before storing it in memory (so it is recalled as the correct value when added with the offset). With that layout simply modify the offset in O(1) time and effectively achieve what you are looking for.

Sean K
  • 774
  • 7
  • 10
0

No. You would need to go through every element and subtract one. Going through every element implies o(n) or linear time. Constant implies you would only need to go through one element.

a[100]={0} is syntactic sugar that appears to be constant but it's actually linear on the backend. See this answer

Community
  • 1
  • 1
Dana
  • 310
  • 3
  • 13
  • I have an array which is filled with numbrs so is it possible? – user6889367 Nov 11 '16 at 03:06
  • Sorry, in actual fact even if you did know the elements ahead of time it's still linear o(n) since you'd have to go through each element anyway. Even if it's not in a loop, you're still accessing each element. So as far as I can see, it can't be done in constant time. – Dana Nov 11 '16 at 03:09
  • a[100]={0}; this expression in c++ allows to initialize me all elements to zero without using the for loop...so is there some similar stuff which can subtract? – user6889367 Nov 11 '16 at 03:13
  • I don't use C++ but I would say that's just syntactic sugar and on the backend there is a loop happening which is linear time. Have a look at this [question](http://stackoverflow.com/questions/303519/initializing-an-n-elements-array-using-o1-performence) which is similar to yours, it should reiterate my points – Dana Nov 11 '16 at 03:24