algorithm - Understanding asymptotic notation when given asymptotic performance, time and number of elements -

-

2nd year computer science student here. in class covering asymptotic notation, sorting algorithms , such. need understanding asymptotic notation , how values relate 1 another. have been @ little while can't seem arrive @ reasonable conclusion. imagine answer simple eludes me. professor provided hand-out goes pretty detail asymptotic notation , how used.

so, hand out asks following questions:

what distinction between big-o , big-theta asymptotic performance?

my conclusions hand-out are:

-big-o performance means algorithm can finish , asymptotic performance worst case scenario.

-big-theta performance means algorithm cannot finish , asymptotic performance best case scenario.

if these assumptions incorrect can sesame street me?

-and-

a wood-chuck requires 20 seconds chuck 60 chucks of wood, , wood-chuck’s wood-chucking algorithm has temporal asymptotic performance theta(n^2). how wood wood-chuck chuck (if wood-chuck chuck wood) in 5 minutes?

i understand since algorithm n^2 can expect amount of time takes chuck more , more wood exponential. don't see how can find amount of wood given in 5 minutes. feel over-thinking , answer simple. appreciated.

if know have o(n^2) algorithm , can x units of work in y seconds, can 2x units of work in approximately 4y seconds. can 4x units of work in approximately 16y seconds.

or, amount of work can in 16*y seconds equal x*sqrt(16).

so amount of work can in z seconds x*sqrt(z). square root of 15 approximately 3.873, meaning can 60*3.873, or 232.46 units of work in 15 seconds.

it's important remember, though, you're working approximations here. asymptotic "math" doesn't give exact numbers. doing exercise in real life (and have done quite similar), i'd estimate 4 times work in 300 seconds did in 20 seconds, because 300 approximately 16 times time.

so answer question "approximately 240 chucks."


Comments

Post a Comment

Popular posts from this blog

php - How to display all orders for a single product showing the most recent first? Woocommerce -

-
i have password protected page on frontend. on page, want display full list of purchases associated single woocommerce product id. option 1: i've looked through woocommerce docs , , found: wc_cli_order , list_( $args, $assoc_args ) function lists orders. presumably, orders can filtered product id [--=] filter orders based on order property. line item fields (numeric array, started index zero): line_items.0.product_id option 2: i found article , based on customer id. i've modified code based on guesses meta_key , meta_value. $customer_orders = get_posts( array( 'numberposts' => -1, 'meta_key' => '_product', 'meta_value' => get_product_id(), 'post_type' => wc_get_order_types(), 'post_status' => array_keys( wc_get_order_statuses() ), ) ); how display orders single product showing recent order first? here solution put based on these articles: http://www.w...
Read more

asp.net - How to correctly use QUERY_STRING in ISAPI rewrite? -

-
i'm having difficult time , hope guys can help. using helicon isapi rewrite version 3.1.0.104 on our iis server. edit http.conf file , have tried , still fail. this trying do: redirect url: https://www.domain.com/switch-by-version?version=2.8.5.2594 to: https://test.domain.com/load/load.aspx?tver=2.8.5.2594 the version number @ end source url change, , need target url have same version number @ end of url example above shows. i tried following not work: rewritecond %{query_string} ^version=(\d\d?)\.(\d\d?)\.(\d\d?)\.(.*)$ [nc] rewriterule ^/switch-by-version(.*)$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l] any appreciated! thanks. if it's running in equivalent context of .htaccess , rule shouldn't start / . here's simpler version: rewritecond %{query_string} ^version=(\d+\.\d+\.\d+(?:\..+)?)$ [nc] rewriterule ^switch-by-version/?$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l]
Read more

angularjs - How restrict admin panel using in backend laravel and admin panel on angular? -

-
https://scotch.io/tutorials/token-based-authentication-for-angularjs-and-laravel-apps following tutorials, try write authentication restrict admin panel, didn't understood how can that. this admin panel, admin panel don't want show , request database unauthenticated users. my laravel-routes route::get('/admin',function(){ return view('index'); }); route::get('/api/v1/employees/{id?}', 'employees@index'); route::get('/api/v1/users/{id?}', 'employees@users'); route::post('/api/v1/employees', 'employees@store'); route::post('/api/v1/employees/{id}', 'employees@update'); route::delete('/api/v1/employees/{id}', 'employees@destroy'); route::group(['prefix' => 'api'], function() { route::resource('authenticate', 'authenticatecontroller', ['only' => ['index']]); route::post('authenticate', 'authentic...
Read more