CODEWITHSUNDEEP
c++stringbig-ospace-complexity
James Wilks
James Wilks

Reputation: 740

Time Complexity in Reversing a C++ String

I have a problem on my homework to reverse the words in a C++ string, in place, with only O(1) additional memory. I'm confused by what it means O(1) additional memory. I understand what O(1) generally means, where no matter how big the input is, the time to compute will be constant so I'm guessing I should add only one piece of memory that would keep track of the words in reverse. Any suggestions?

Upvotes: 2

Views: 1888

Answers (1)

templatetypedef
templatetypedef

Reputation: 373112

O(1) additional memory means "using at most some constant additional memory." For example, you couldn't store a copy of the string, since that would take O(n) space, but you could store any constant number of extra ints, chars, etc.

More generally- statements like "O(1)" or "O(n)" don't necessarily refer to runtimes. Big-O notation is a way of describing functions. An algorithm can't be O(n), but its runtime can be O(n). An algorithm's space usage can similarly be O(1), O(n), O(2n), etc.

Hope this helps!

Upvotes: 2

Related Questions