algorithm - Space Complexity and Modifying the Data Set -

-

what space complexity of following algorithm?

given array of n 32-bit signed integers, each value positive , less 2 power of 30, negate values in array, negate values in array second time.

the question arose me out of discussion in comment section here: rearrange array arr[i] becomes arr[arr[i]] o(1) space

i interested in different opinions , definitions. think subtle distinctions , definitions may missing in stackoverflow discussions on subject.

space complexity refers added space requirements algorithm, on , above original data set itself. in case, original data set n 32-bit signed integers, you're concerned storage above that.

in case, storage is nothing, translates constant o(1) space complexity.

if required create separate array (negated, negated again), o(n) since space required in proportion original data set.

but, since you're doing negations in-place, that's not case.


Comments

Post a Comment

Popular posts from this blog

PHPMotion implementation - URL based videos (Hosted on separate location) -

-
i have implement video collection website users of specific isp. site hosted on public web-server movies hosted on local isp server. user of isp + general visitors can see available movies; isp's users able play them. player on site point url of local machine ( http://192.x.x.x/movies/mymovie.mov ) private class (192.x.x.x) accessible isp user. question: possible phpmotion script? or need custom work. if possible, can please suggest available mods? phpmotion require modifications able handle this. uploading, conversion, thumbnail generation, , playback pretty static in phpmotion. really though, rather modding entire upload , conversion process, if created quick custom form add entries phpmotion database (maybe include thumbnail upload), tweaked playback paths, should go on phpmotion side of things. assume had videos in format player handle (such flv or mp4).
Read more

javascript - Using Windows Media Player as video fallback for video tag -

-
getting video play cross platform using example video.js bit of fuss. in days when video should embedded use embed windows media player, work out of box on windows. since it's today old ie on windows doesn't support video tag experimented using windows media player fallback, , work well. what wonder here is, why haven't else solution? have missed something? code small, there's no flash files, cross domain issues or need of server working. works. so before develop further , add custom control , subtitles support wonder say. the code looks this: <video id="myvideo" style="width:640px; height: 360px;" autoplay data-wimpsource="http://esd.volvocars.com/dc/cdn/video/birds-on-a-wire.mp4"> <source src="http://esd.volvocars.com/dc/cdn/video/birds-on-a-wire.mp4" type="video/mp4" /> <source src="http://esd.volvocars.com/dc/cdn/video/birds-on-a-wire.webm" type="video/webm" />
Read more

c# - Unity IoC Lifetime per HttpRequest for UserStore -

-
i'm trying clean default implementation of accountcontroller.cs comes out of box in new mvc5/owin security implementation. have modified constructor this: private usermanager<applicationuser> usermanager; public accountcontroller(usermanager<applicationuser> usermanager) { this.usermanager = usermanager; } also, have created lifetime manager unity looks this: public class httpcontextlifetimemanager<t> : lifetimemanager, idisposable { private httpcontextbase _context = null; public httpcontextlifetimemanager() { _context = new httpcontextwrapper(httpcontext.current); } public httpcontextlifetimemanager(httpcontextbase context) { if (context == null) throw new argumentnullexception("context"); _context = context; } public void dispose() { this.removevalue(); } public override object get
Read more