big o - Big O - Time Complexity puzzling for while loops -


as time complexity example (refreshing mind) attempting solve find running time (in terms on n) of following algorithm:

for (i=1; <= n; i++) {      //o(n)   k = 1;   (j=1; j <= i; j++) {    //o(n)     k = 2*k;   }   j = k*k;   while (j > 1) {             //o(..?)     j = j / 2;   } }

i understand first 2 loops combined take o(n^2), little perplexed @ how find running time of while loop. although know while loop runs twice first execution, 4 times, 6... multiples of 2. make run o(nlog(n)) times?

the repeated division log_2(j) same log(j) / log(2). log(2) constant, it's written log(j).

because o(log(n)) @ same depth o(n) loop , o(n) loop dwarfs o(log(n)) loop, 2 combined takes o(n) time.

the final time complexity o(n^2).


Comments

Post a Comment

Popular posts from this blog

resizing Telegram inline keyboard -

telegram's inline keyboard great feature lots of different use cases. inline buttons added list of items this: inline_keyboard = [[inlinekeyboardbutton(text="button", callback_data="button"), inlinekeyboardbutton(text="reset",callback_data="reset")]] inline_keyboard_markup = inlinekeyboardmarkup(inline_keyboard) update.message.reply_text("hi", reply_markup=inline_keyboard_markup) the above code adds 2 buttons each half width of chat screen. i know the normal keyboard button there resize_keyboard parameter somehow can used. my question is there way resize inline buttons ? example make full width or quarter width. unfortunately, can't now. :( you can suggest @botsupport , might add feature next version.
Read more

javascript - How to bind ViewModel Store to View? -

i'm pretty new ext js , trying embed multiselect inside panel . the viewmodel has stores property can see here: ext.define('test.view.controls.search.searchfiltermodel', { extend: 'ext.app.viewmodel', alias: 'viewmodel.filter', data: { title: '' }, stores: { test: { fields: [ 'id', 'name' ], proxy: { type: 'ajax', url: 'api/test', reader: 'array' }, autoload: true } } }); i bind in view this: viewmodel: { type: 'filter' }, layout: 'fit', border: 1, plain: true, scrollable: 'y', layout: 'fit', bind: { title: '{title}', }, items: { xtype: 'multiselect', scrollable: false, allowblank: true, ddreorder: true, bind: { store: '{test}' }, valuefield: 'id', displayfield: 'name' } ...
Read more

c - Why does alarm() cause fgets() to stop waiting? -

i playing around signals in c. main function asks input using fgets(name, 30, stdin) , , sits there , waits. set alarm alarm(3) , , reassigned sigalrm call function myalarm calls system("say pay attention") . after alarm goes off, fgets() stops waiting input , main fn continues on. happens if change myalarm set variable , nothing it. void myalarm(int sig) { //system("say pay attention"); int x = 0; } int catch_signal(int sig, void (*handler)(int)) { // when signal comes in, "catch" , "handle it" in way want struct sigaction action; // create new sigaction action.sa_handler = handler; // set it's sa_handler attribute function specified in header sigemptyset(&action.sa_mask); // "turn signals in sa_mask off?" "set sa_mask contian no signals, i.e. nothing masked?" action.sa_flags = 0; // not sure, looks aren't using of available flags, whatever may return sigaction(sig, ...
Read more