java - O-notation with for-loop with modulo condition -


my question how calculate o-notation operation, 2 outer loops go o(n^3) times. question o-notation going when modulo used in condtion , inner for-loop runs when factor in j.

for(int = 1 ; <= n ; i++) {    for(int j =1; j <= ∗ ; j++) {       if(j % == 0 ) {          for(int k = 0 ; k < j ; k++ ){              sum++;          }        }     } }

it o(n^4).

the trick 1 if (j % == 0). since i pretty n , j going range n^2 know statement true n + (n-1) + ... + 1 times going simplify (n+1)(n+2)/2 or o(n^2) in turn run loop runs n^2 times. need treat addition, have n^3 + n^2 * n^2, simplifies o(n^4).

if there fault in reasoning please point out, little rusty.


Comments

Post a Comment

Popular posts from this blog

javascript - WinJS appendTextAsync producing scheduler errors -

im trying implement logger in uwp app (windows 10) following code in both this , this answers. i'm afraid in both cases end getting scheduler ( winjs.utilities.scheduler ) errors @ random times (couldn't establish pattern). main problem the application freezes sometimes , suspect due log implementation because final line reads transitioning job (1) from: running to: blocked when happens. i messages like transitioning job (1) from: blocked_waiting to: cooperative_yield transitioning job (1) from: cooperative_yield to: scheduled in middle of execution, varying states. initialization method this.init = function () { let logger = new winjs.promise(function (complete) { let = new date(); let logfilename = `log-${now.getdate()}-${now.getmonth() + 1}-${now.getfullyear()}.log`; localfolder .createfolderasync("logs", windows.storage.creationcollisionoption.openifexists) .then(fun...
Read more

minify - Minimizing css files -

i want know how css files can minimized. currently, using external sites css minifier compress css files. however, after removing whitespaces, comments, etc, file sizes reduced 10-15%. how frameworks bootstrap manage make minimized versions kilobytes. as example, css is: body { background-color: #ff0; } the reduction goes 28 bytes 22 bytes other css files have lot more characters still smaller this. actually minifying code means it's remove thing code white space characters new line characters comments block delimiters it reduces amount of code has transferred on web , speed site load fastly.but unreadable format.
Read more

Sockets with kotlin -

i looking develop application in kotlin uses sockets, unfortunately kotlinx sockets broken , not far connect current kotlin 1.1 co-routines. (i see noted unanswered issue on github @sundwarf on july 16 already) specifically, sample code kotlinx.sockets uses connect in form: asocket().tcp().connect(inetsocketaddress(inetaddress.getbyname("google.com"), 80)) which fails noted trace here . i looking either sample of connect work, or recommendation of alternate package kotlix.sockets. there many kotlin apps making use of sockets, either there alternatives kotlinx.sockets or there way around connect problem.
Read more