algorithm - Time Complexity for Quick sort -



algorithm - Time Complexity for Quick sort -

suppose b(n) , w(n) respectively best case , worst case asymptotic running times sorting array of size n using quick sort.

now consider 2 statements:(i) b(n) o(w(n)) (ii) b(n) theta(w(n))

among these 2 1 right statement?

ps: worst case : n^2 best case : nlogn

what think true b(n) smaller w(n), can b(n) have same order of growth of w(n)

the former correct. trick less complex classes subsets of more complex classes, algorithms run in o(n) run in o(n^2). theta tighter bound, in case of quicksort tight capture b(n).

algorithm time-complexity quicksort

Comments

Post a Comment

Popular posts from this blog

assembly - What is the addressing mode for ld, add, and rjmp instructions? -

assembly - What is the addressing mode for ld, add, and rjmp instructions? - hey guys know ldi (load immediate) addressing mode set immediate , st instruction addressing mode set index. however, have no thought others curious are! thanks :) the addressing modes explained in instruction set, in first few pages. in table of instructions see operands instruction determine addressing mode. mode indicated arguments assembly instruction. for example, ld had several different ways of operating, depending on arguments. 1 of them ld rd,x d number of register, such ld r3,x . ld r3,-z else (although both indirect addressing). rjmp k relative addressing, jumping pc + k + 1. add rr,rd direct register addressing. result contained in rd. assembly avr instructions
Read more

vowpalwabbit - Interpreting Vowpal Wabbit results: Why are some lines appended by "h"? -

vowpalwabbit - Interpreting Vowpal Wabbit results: Why are some lines appended by "h"? - below part of log training vw model. why of these lines followed h? you'll notice that's true of "average loss" line in summary @ end. i'm not sure means, or if should care. ... average since illustration illustration current current current loss lastly counter weight label predict features 1.000000 1.000000 1 1.0 -1.0000 0.0000 15 0.500000 0.000000 2 2.0 1.0000 1.0000 15 1.250000 2.000000 4 4.0 -1.0000 1.0000 9 1.167489 1.084979 8 8.0 -1.0000 1.0000 29 1.291439 1.415389 16 16.0 1.0000 1.0000 45 1.096302 0.901166 32 32.0 -1.0000 -1.0000 21 1.299807 1.503312 64 64.0 -1.0000 1.0000 ...
Read more

ubuntu - Bash Script to Check That Files Are Being Created -

ubuntu - Bash Script to Check That Files Are Being Created - we have amazon ec2 instance upload output our security cameras. every , then, cameras have issue, stop uploaded, , need rebooted. easy way determine seeing if files not beingness created. problem creates lots , lots of files. if utilize find -ctime, takes long time script run. there faster way check see if files have been created since yesterday? need capture result, (yes there files, or not there not,) , email message, nice have didn't take half hr run. #!/bin/bash find /vol/security_ftp/west -ctime -1 find /vol/security_ftp/backentrance -ctime -1 find /vol/security_ftp/boardroomdoor -ctime -1 find /vol/security_ftp/mainentrance -ctime -1 find /vol/security_ftp/north -ctime -1 find /vol/security_ftp/south -ctime -1 using find natural solution, if must avoid it, can see newest file in directory using ls , sorting output according ctime, eg. ls /vol/security_ftp/west -clt | head --lines=1 ...
Read more