math - Time complexity of a function with time 1 + 8 + 27 + 64 + ... + sqrt(n)^3? -

-

i have been told that

1 + 8 + 27 + 64 + ... + (√n)3 = θ(n2)

why case?

to make sure understand you're saying, curious in why sum

13 + 23 + 33 + ... + (√n)3 = θ(n2)

one way a formula sum of first m cubes. equal to

(m(m + 1) / 2)2

so let's plug in m = √n, gives

13 + 23 + 33 + ... + (√n)3

= ((√n)((√n) + 1) / 2)2

= ((n + √n) / 2)2

= (n2 + 2n√n + n) / 4

this final expression gives exact value of sum of first √n perfect cubes. note expression θ(n2), because n2 dominant term.

hope helps!


Comments

Post a Comment

Popular posts from this blog

Winapi c++: DialogBox hangs when breaking a loop -

-
i've created s simple w32 application cicle through 2 applications(hard coded window classes atm). when call start button (idc_start) works fine, when change focus hwnd application hangs cannot closed. need simple , clean method stop loop, start when calling idc_start. apreciated! #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <windows.h> #include <resource.h> #include <iostream> using namespace std; bool callback dlgproc(hwnd hwnd, uint message, wparam wparam, lparam lparam) { hwnd hwnd1,hwnd2; hwnd1 = findwindow("notepad++",0); hwnd2 = findwindow("notepad",0); bool bdone; switch(message) { case wm_initdialog: // set dialog box, , initialise default values { setdlgitemint(hwnd, idc_number, 5, false); hicon hicon, hiconsm; hicon = (hicon)loadimage(null, "e32.ico", image_icon, 32, 32, lr_loadfromfile); if(hicon) se...
Read more

vb.net - Font adding using PDFsharp -

-
i using pdfsharp add text pdf. when use below code add following text these fonts facing problem. after pdf created using pdfsharp , when opened in adobe reader getting message "cannot find or create font 'windings'. characters may not display or print correctly." opens the source pdf trying modify has fonts helvetica , windings(embedded) this part of code adds text pdf dim font xfont = new xfont("verdana", 20, xfontstyle.regular) gfx.drawstring("hello, world!", font, xbrushes.black, new xrect(0, 0, page.width, page.height), xstringformats.center) font = new xfont("wingdings", 20, xfontstyle.regular) gfx.drawstring("llll", font, xbrushes.black, new xrect(25, 15, page.width, page.height), xstringformats.center) font = new xfont("helvetica", 20, xfontstyle.regular) gfx.drawstring("abcd", font, xbrushes.black, new xrect(50, 25, page.width, page.height), xstringformats.center) after using code text ge...
Read more

javascript - jQuery iScroll clickable list elements while retaining scroll? -

-
is possible have clickable elements? such list elements? while using iscroll? seems short of button, or maybe link can't click on element make something. had similar issue inputs well. enough searching able find solution helped me place work inputs. have need have scrollable ui while having ability click on thats not button or link, such li contained within specific uls. so wondering if there way of having iscroll tell difference between click or tap rather vs scroll, , such have action desired.
Read more