data structures - time-complexity of nested loop -


why time-complexity of

function (n) {     //this loop executes n times      for( = 1 ; <= n ; + + )     //this loop executes j times j increase rate of     for( j = 1 ; j <= n ; j+ = )     print( “*” ) ;  }

its running time n*(n^1/2)=n^3/2

so, o(n^3/2)

please explain mathematical steps.

thank in advance.

the running time bounded o(n^{3/2}), that's not tight!

notice inner loop makes o(n/i) iterations each i=1,2,...n), time complexity o(n * (1 + 1/2 + 1/3 + ... + 1/n)) = o(n log n).

this because 1+1/2+1/3+...+1/n=o(log n) well-known harmonic series.


Comments

Post a Comment

Popular posts from this blog

sql - can we replace full join with union of left and right join? why not? -

can replace full join union of left , right join? if no,why? 'yes' if t1 , t2 sets (no duplicated rows), otherwise answer 'no'. create table t1 (i int); create table t2 (i int); insert t1 values (1); insert t1 values (2); insert t1 values (2); insert t2 values (3); full join select * t1 full join t2 on t1.i=t2.i order 1,2 1 (null) 2 2 2 2 (null) 3 union select * t1 left join t2 on t1.i=t2.i union select * t1 right join t2 on t1.i=t2.i order 1,2 1 (null) 2 2 (null) 3 union all select * t1 left join t2 on t1.i=t2.i union select * t1 right join t2 on t1.i=t2.i order 1,2 1 (null) 2 2 2 2 2 2 2 2 (null) 3
Read more

javascript - Parallax scrolling and fixed footer code causing width issues -

i bolted bits of code. 1 parallax scrolling, , other piece of fixed footer code found here: http://codepen.io/madshaakansson/pen/cgjch though after bolting , fixing few issues, have problem different widths. header different width footer, , main content doesnt span whole width of page. have tried adjusting width of content css 100%, made main content span whole width, ended breaking footer. i not sure need change make these different bits of code work together. advice appreciated. my attempt: http://codepen.io/dingerzat/pen/qgbwkk html /*global define: false */ function init() { window.addeventlistener('scroll', function(e) { var distancey = window.pageyoffset || document.documentelement.scrolltop, shrinkon = 300, header = document.queryselector("header"); if (distancey > shrinkon) { classie.add(header, "smaller"); } else { if (classie.has(header, ...
Read more

iOS: Performance of reloading UIImage(name:...) -

i have tableview , each row has icon. 90% of rows have same icon. in cellforrowatindexpath method load image assets folder this: var cellimage = uiimage(named: "myimage") does pose performance problem? os somehow smart enough it's same image each time? better if loaded image once , saved in class variable , assigned each time? uiimage 's named: api does kind of caching. if @ uiimage's documentation , states: use init(named:in:compatiblewith:) method (or init(named:) method) create image image asset or image file located in app’s main bundle (or other known bundle). because these methods cache image data automatically, recommended images use frequently.
Read more