algorithm - What is wrong with this reasoning to determine the upper bound? -

-

i given question in algorithm class

is 2^{2n} upper bounded  o(3^n)?

now clear 2^2n 4^n, , 4^n can't upper bounded 3^n.

however if take log on both sides

on lhs 2n on rhs kn (where k constant)

2n can upper bounded kn, contradicting of more obvious claim above. doing wrong in reasoning?

essentially, reasoning boils down statement:

if log f(n) ≤ c log g(n) constant c, f(n) = o(g(n)).

this statement isn't in general true statement, though. 1 way see find counterexamples:

  • if f(n) = n4 , g(n) = n, log f(n) = 4 log n , log g(n) = log n. it's true there's multiple of log n that's bigger 4 log n, n4 ≠ o(n).

  • if f(n) = 4n , g(n) = 2n, log f(n) = 2n , log g(n) = n. there's multiple of n makes bigger 2n, 4n ≠ o(2n).

to @ why doesn't work, notice c log g(n) = log g(n)c, multiplying log constant equivalent raising original function large power. can reason big-o of function multiplying constant, can't reason raising power, why reasoning breaks down.


Comments

Post a Comment

Popular posts from this blog

c - How to retrieve a variable from the Apache configuration inside the module? -

-
i'm building custom apache module. how retrieve variable apache configuration inside module? see variable "some_var_config_from_apache_or_htaacess" inside apache module: /* source: http://people.apache.org/~humbedooh/mods/examples/mod_example_1.c */ /* include required headers httpd */ #include "httpd.h" #include "http_core.h" #include "http_protocol.h" #include "http_request.h" static void register_hooks(apr_pool_t *pool); static int example_handler(request_rec *r); /* define our module entity , assign function registering hooks */ module ap_module_declare_data example_module = { standard20_module_stuff, null, // per-directory configuration handler null, // merge handler per-directory configurations null, // per-server configuration handler null, // merge handler per-server configurations null, // directives may have httpd register_hoo
Read more

c# - Constructor arguments cannot be passed for interface mocks -

-
when debug code , read line mocklessonplannerafactory creation error: constructor arguments cannot passed interface mocks. var mockschoolclasscodeservice = new mock<ischoolclasscodeservice>(); var mockdateservice = new mock<idateservice>(); var mocklessonplannerafactory = new mock<ilessonplannerafactory>(mockdateservice.object); var mocklessonplannerbfactory = new mock<ilessonplannerbfactory>(mockdateservice.object); var service = new timetableservice(mockunitofwork.object, mocklessonplannerafactory.object, mocklessonplannerbfactory.object, mockschoolclasscodeservice.object); my timetableservice accepts instances of interface type only. mocklessonplannerafactory , bfactory... want in constructor idateservice passed. what wrong code? the clue in error message "constructor arguments cannot passed interface mocks." the mock created interface have default constructor because interfaces don't have constructor. remember mockin
Read more

python - malformed header from script index.py Bad header -

-
i want run python code in apache2(ubuntu 14.04) server. have followed these steps , getting error: step 1: configuration 1: have created directory , file under /var/www/cgi-bin configuration 2 : have edited /etc/apache2/sites-available/000-default.conf alias /cgi-bin /var/www/cgi-bin <directory "/var/www/cgi-bin"> options indexes followsymlinks execcgi addhandler cgi-script .cgi .py allow </directory> <directory /var/www/cgi-bin> options </directory> step 2: and python script is: index.py #!/usr/bin/env python import cgi; import cgitb;cgitb.enable() print "content-type: text/plain\n" print "<b>hello python</b>" step 3: when ran through chrome browser using: url : http://localhost/cgi-bin/index.py step 4: i getting error in error-log malformed header script 'index.py': bad header: hello python you should end header \r\n, must print out yet \r\n signal body coming. (i
Read more