You are viewing a single comment's thread. Return to all comments →
Yeah, my bad. It's O(1) per query, but an O(n) space complexity algorithm in the end.
No,the algorithmn(which is the main part)is of O(1) time complexity you cannot optimize it any further. Space complexity is also optimized you cannot avoid using an array as the problem is based on it.
You cannot say that. And you cannot call it O(1),
For example if a problem asks us to sum up all numbers in an array, we can simply take an input and add it to a variable sum, or we can take all inputs in an array. What you just said implies that we cannot distinguish between these 2 algorithms, but we can(One is O(1), other is O(n).
Of course it isn't sensible to assume that we can solve this problem without the array in this particular case, but I still think that O(1) complexity is wrong.
Again you misunderstood what i am saying. I am saying that the algorithmn part(i.e. the if and else statment) is O(1) not the whole code, since in this problem we cannot run away from array. And i am claming that my solution is the most optimized one.
And BTW the example that you gave has O(n)time complexity not O(1) since for ever new element you are doing a computational opperation(i.e. adding the sum and the new input)
I'm talking about space complexity. The space complexity is not O(1), and the space complexities in my 2 examples were different(one is O(n) as we are using a WHOLE n element array, while in the other we're using one variable).
You on the other hand, are talking about the time complexity. It is O(1) per query and that's correct. But how is space in any way O(1) ? There exists an n element array.
Seems like we missunderstood each other. I was talking about time complexity the whole time. As for the space complexity yes it is O(n), O(1) is not possible in this problem since we have to store the elements.
hi bro,i am a beginner.How to understand these concepts of time complexity and space complexity.
You should not worry about these things if you are a beginner,but since you have asked i have explained it here, take a look.
In the beginning your focus should be to complete the task without worrying about these time/space complexities.
My pleasure :)