Hello
2010/12/3 Prims :
> I believe the maximum space needed in the hashtable is O(max positve -
> (max negative value).
I use the same algorithm as you do and I think you could use a smaller
space by handling collisions. So the space complexity might be O(N)
--
You received this message becaus
Hello Algoose
I believe the maximum space needed in the hashtable is O(max positve -
(max negative value).
Since the possible cumulative sum is of that order. Correct me if i am
wrong
On Dec 2, 12:00 pm, Algoose chase wrote:
> I believe the space complexity should be O(n) since you need to store
I believe the space complexity should be O(n) since you need to store the
cumulative sum corresponding to each of the elements from the input starting
from the first element.
On Wed, Dec 1, 2010 at 12:04 AM, Prims wrote:
> I got the solution to use a hash table storing partial sums a[0],
> a[0]+
Note, this involves O(N) EXPECTED time, not worst.
On 30 ноя, 21:34, Prims wrote:
> I got the solution to use a hash table storing partial sums a[0],
> a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i
>
> Whenever a collision happens, then it is the sub array from i to the
> last sum
I got the solution to use a hash table storing partial sums a[0],
a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i
Whenever a collision happens, then it is the sub array from i to the
last summand.
This involves O(N) Time complexity but i what is the space complexity
in this case?
O
