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

php - How to add and update images or image url in Volusion using Volusion API -

actually have store importing products store product data insert , update image or image url not insert , update. this xml code name datapro.txt. <products_joined> <productcode>3710_012t</productcode> <vendor_partno>eah5450silent/di/1gd3(lp)</vendor_partno> <productname>test product ta</productname> <hideproduct>n</hideproduct> <stockstatus>20</stockstatus> <lastmodified>1/5/2016 10:25:00 am</lastmodified> <lastmodby>2</lastmodby> <productweight>0.9</productweight> <productprice>100</productprice> <productmanufacturer>asus tek</productmanufacturer> <vendor_price>32.69</vendor_price> <numproductssharingstock>0</numproductssharingstock> <categoryids>107</categoryids> <producturl>http://tebkq.mvlce.servertrust.com/productdetails.asp?productcode=3710_012t</producturl>
Read more

javascript - jQuery UI Splitter/Resizable for unlimited amount of columns -

using jqueryui splitter or resizable functions want create layout allows unlimited amount of columns added , columns need resizable. so fiddle: https://jsfiddle.net/f3glh3mw/ but in fiddle html contains out of nested sets instead of inline. limits possibilities above fiddle can have equal widths 2,4,8,16,32 etc columns. in between shows crooked can see in fiddle. when researching came on question: jquery ui , splitter if @ top answer shows structure like: <div class="wrap"> <div class="resizable resizable1"></div> <div class="resizable resizable2"></div> </div> full fiddle: http://jsfiddle.net/8qztj/86/ which structure want javascript hardcoded 2 resizable items. so here question: how modify last fiddle works amount of .resizable divs. or know of plugin can this. thanks helping! so far found plugin: http://www.bacubacu.com/colresizable/ which says , close functionality want. in
Read more

javascript - IE9 error '$'is not defined -

Image
<!--[if lte ie 9]><html class="lte9"><![endif]--><!--[if gt ie 9]><html><![endif]--> <!--[if !ie]><!--> <html> <!--<![endif]--> blah blah <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.1/jquery.min.js"></script> <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script> <script src="{{ asset('js/mypage.js') }}" type="text/javascript"></script> </body> </html> when load page, ie9 brings error '$' not defined . how can solve error? +++ mypage.js $(function(){ //when load page, //ie9 tag not moving. $(window).load(function() { $('div.mask').hide(); }); // when click , willshow show. //for not ie 9 if (!$('html').hasclass('lte9')) { var = $('ul.about > li > span.activebtn');
Read more