algorithm - Solving the similar recurrence: T(n) = 3T(n/3) + n/3 -

-

given..

t(0) = 3 n <= 1  t(n) = 3t(n/3) + n/3 n > 1

so answer's suppose o(nlogn).. here's how did , it's not giving me right answer:

t(n) = 3t(n/3) + n/3  t(n/3) = 3t(n/3^2) + n/3^2

subbing t(n) gives..

t(n) = 3(3t(n/3^2) + n/3^2) + n/3  t(n/3^2) = 3(3(3t(n/3^3) + n/3^3) + n/3^2) + n/3

eventually it'll like..

t(n) = 3^k (t(n/3^k)) + cn/3^k

setting k = lgn..

t(n) = 3^lgn * (t(n/3^lgn)) + cn/3^lgn  t(n) = n * t(0) + c  t(n) = 3n + c

the answer's o(n) though..what wrong steps?

t(n) = 3t(n/3) + n/3 t(n/3) = 3t(n/9) + n/9  t(n) = 3(3t(n/9) + n/9) + n/3      = 9t(n/9) + 2*n/3      //statement 1  t(n/9)= 3t(n/27) + n/27 t(n)  = 9 (3t(n/27)+n/27) + 2*n/3 // replacing t(n/9) in statement 1       =  27 t (n/27) + 3*(n/3)  t(n)  = 3^k* t(n/3^k) + k* (n/3) //

replace k log n base 3.

t(n)  = n t(1) + (log n) (n/3); // t(1) = 3 t(n)  = 3*n + (log n) (n/3); hence , o (n* logn)

Comments

Post a Comment

Popular posts from this blog

How to access named pipes using JavaScript in Firefox add-on? -

-
i'm trying access named pipe in firefox add-on. code, based on solution 2 this codeproject question, is: var file = components.classes["@mozilla.org/file/local;1"].createinstance(components.interfaces.nsilocalfile); file.initwithpath("\\\\.\\pipe\\test"); var text = "some text written"; var writer = components.classes["@mozilla.org/network/file-output-stream;1"].createinstance(components.interfaces.nsifileoutputstream); // open file read/write access, , create if not exist. writer.init (file, 0x04 | 0x08, -1, 0); writer.write (text, text.length); writer.flush (); writer.close (); when run firefox scratchpad, get: /* exception: component returned failure code: 0x80520012 (ns_error_file_not_found) [nsifileoutputstream.init] @6 */ line 6 line call writer.init. i've played passing different flags writer.init, no luck. i'm able write normal file path code, not named pipe path. i've been searching more information of da...
Read more

multithreading - OPAL (Open Phone Abstraction Library) Transport not terminated when reattaching thread? -

-
i in process of writing application using opal makes h323 calls. have looked online number of working examples , have managed put resembles should like, @ present able call external ip via application when accept call craps out , dies. leaving me with: 0:12.949 setupcall:8752 sert.cxx(259) assertion fail: transport not terminated when reattaching thread , file d:\voip\software\opal\src\opal\transports.cxx, line 1021 passertfunc(0xde3f88, 0xffffffffd228226f, 0, 0) + 0x82 passertfunc(0x10d6e5f8, 0x3fd, 0, 0x10d6eb98) + 0x15b opaltransport::attachthread(0xde5870, 0xffffffffd22fc76b, 0, 0) + 0x96 h323connection::setupconnection(0xffffffffd22fc713, 0, 0, 0xde6ea8) + 0x196 asynchcallsetup(0x10d3572c, 0, 0, 0xdd0108) + 0x7c pthread1arg<psafeptr<opalconnection,psafeptrbase> >::main(0xffffffffd2282faf from have deduced, perhaps incorrectly if there thread lock issue caused (possibly arising fact application sending expected h323 call, throwing in c...
Read more

node.js - req param returns an empty array -

-
i using node.js , mongodb geolocation app , req param returns empty array exports.findpressure = function(req, res) { var queryobject = req.param('q'); console.log(queryobject); db.collection('pressure', function(err, collection) { collection.find( { loc: { $near :[ req.param('q') ] , $maxdistance : 5 }},{"value" : 1, _id : 0}) .sort({_id : -1}).limit(1).toarray(function(err, items) { res.send(items); }); }); }; the longitude , latitude values displayed in console listening on port 3000... connected 'weather' database 8.9068256,52.019347499999995 /pressure?q=8.9068256,52.019347499999995 200 27ms - 2b the url follows http://localhost:3000/pressure?q=8.9068256,52.019347499999995 if use values 8.9068256,52.019347499999995 getting value database if use req.param('q') returning empty array you seem passing values part of query string. req.query.q should contain comma-s...
Read more