algorithm - How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n) -

-

i know how recurrence relations algorithms call once, i'm not sure how calls multiple times in 1 occurrence.

for example:

t(n) = t(n/2) + t(n/4) + t(n/8) + (n)

use recursion tree. see last example of recursion tree @ clrs "intro algorithm".

t(n) = t(n/2) + t(n/4) + t(n/8) + n. root n(cost) & divided 3 recursions. recursion tree looks follows:

t(n) = n = n t(n/2)t(n/4)t(n/8) (n/2) (n/4) (n/8) t(n/4)t(n/8)t(n/16) t(n/8)t(n/16)t(n/32) t(n/16)t(n/32)t(n/64)

                                             n---------------------------------> n                                     (n/2)         (n/4)           (n/8)--------------> (7/8)n                           n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n                                             ...

longest path: leftmost left branch = n -> n/2 -> n/4 -> ... -> 1

shortest branch: rightmost right branch = n -> n/8 -> n->64 -> ... -> 1

the number of leaves (l): 3^log_8(n) < l < 3^log_2(n) => n^0.5 < l < n^1.585

look @ tree - upto log_8(n) levels tree full, , go down, more & more internal nodes absent. theory can give bound,

t(n) = big-oh (summation j=0 log_2(n)-1 (7/8)^j n) = ... => t(n) = o(n). t(n) = big-omega (summation j=0 log_8(n)-1 (7/8)^j n) = ... => t(n) = big-omega(n).

therefore, t(n) = theta(n).

here points are: t(n/2) path has highest length...

this must not complete ternary tree ... height = log base 2 of n & # of leaves must less n ...

hope, way u can solve prob.


Comments

Post a Comment

Popular posts from this blog

php - What is the difference between $_SERVER['PATH_INFO'] and $_SERVER['ORIG_PATH_INFO']? -

-
what’s difference between $_server['path_info'] , $_server['orig_path_info'] ? how use them? when run print_r($_server) , path_info , orig_path_info not present in array. why not? how can enable them? i have read php manual on them, still don’t understand them. the path_info variable present if invoke php script this: http://www.example.com/phpinfo.php/hello_there it's /hello_there part after .php script. if don't invoke url that, there won't $_server["path_info"] environment variable. the porig_ prefix uncommon. path_info standard cgi-environment variable, , should never prefixed. did read that? (there issues around php3/php4 if invoked php interpreter via cgi-bin/ - hardly has such setups today.) for reference: http://www.ietf.org/rfc/rfc3875
Read more

fortran - Function return type mismatch -

-
i'm attempting recode old c++ program in fortran make use of lapack (i'm aware c++ have lapack++, i'm having lot of trouble installing it, gave up). i didn't have problems compilation, when had variables declared real . when started coding section of program required lapack, found parameters passed dsyev need double precision . tried change double precision (including changing hard coded numbers double precision counterparts, i.e. 0.0 -> 0.0d0) when try compile, following error of functions , subroutines i've written: error: return type mismatch of function <function> @ (1) (real(4)/real(8)) i'm not sure coming from, in program has been changed double precision. for example, i've declared following: double precision :: alpha(3),d(3),zeta1,zeta2 double precision :: a1(3),a2(3),d1(3),d2(3) double precision :: pi pi = 3.14159265359d0 alpha = (/0.109818d0, 0.405771d0, 2.22766d0/) d = (/0.444635d0, 0.535328d0, 0.154329d0 /) 10 i=1,3 ...
Read more

queue - mq_receive: message too long -

-
i implementing communication between 2 processes using queue. problem when call function mq_receive, error: message long. i have done following: struct mq_attr attr; long size = attr.mq_msgsize; .... // initializing queue "/gateway" int rc = mq_receive(gateway, buffer, size, &prio); if print size value, size=1, while when print same size program (got same mechanism), not long integer ( -1217186280 )... how can solve error?....so while size = 1, believe it's right "message long" why 1? p.s. have tried put : int rc = mq_receive(gateway, buffer, sizeof(buffer), &prio); but no result. it seems need read docs more carefully. when call mq_receive should pass size of destination buffer. this size must greater mq_msgsize attribute of queue . in addition, seems have error in queue attributes initialisation makes proper mq_receive call impossible. here standard message queue session: fill mq_attr struct ( doc ): struct mq_a...
Read more