CODEWITHSUNDEEP
performancebig-o
everconfusedGuy
everconfusedGuy

Reputation: 2797

basic complexity confusion

I have an algorithm which takes in a 2D array and uses no extra space. So is the space complexity of the algorithm O(n^2) (because I am processing the entire input array) or O(1) (since the algorithm does not use any extra space apart from the input)


In particular, in this question http://www.careercup.com/question?id=4959773472587776 , it does not matter if we use 2 extra 1-dimensional arrays right, since anyway the input space complexity is O(n^2).
Thanks!

Upvotes: 1

Views: 187

Answers (1)

perreal
perreal

Reputation: 98048

Auxiliary space complexity does not include the input space whereas the space complexity does.

For auxiliary space complexity analysis, only consider the extra memory consumption. If your algorithm does not use any extra space then the auxiliary space complexity is O(1).

If the input has size m ( = n x n), and you use 2 arrays of size n, then the auxiliary space complexity will be O(n) (or O(logm)).

For space complexity, since you count the input size, you are right, using 2 arrays will not change the space complexity.

Upvotes: 1

Related Questions