performance - Nested time complexity -


i hope simple question, google did not give me immediate results.

if have function running time o(n log n) , inside function function, taking o(n log n), total running time of function?

say have list of lists.

it takes n log n time find desired list , n log n time again find desired item within list.

something like

find list in n log n time      find element in list in n log n time 

is running time still n log n?

thank in advance.

what if function looks this:

for each element e1 in list                          // (o(n) time)       if e1 1 looking           each element e2 in e1                    // (o(n) time)               

it o(n) inside o(n), second o(n) executed once in first loop.

it depends how call second function.

if execute function finds list within list of lists in o(n log n) time , searches just 1 list desired element, finds in o(m log m) time, total running time o(n log n + m log m).
if m=n total time o(n log n).

if outer loop performs o(n log n) "steps", , @ each step consider 1 list list of lists , call function takes o(m log m) time find desired item in list, total running time o(mn (log m)(log n)). i'm having difficulty imagining application use algorithm this, however.

if execute loop o(n) times, , during @ one of iterations of loop execute "inner" loop runs in o(m) time, total running time of outer loop o(n + m). note reason o(m + n) don't have other information in paragraph grows faster, m or n, , o(m + n) covers in either case. again, if knew m=n, or if knew m o(n) (doesn't grow faster n), write total time o(n).


Comments

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

openid - Okta: Failed to get authorization code through API call -

thorough guide for profiling racket code -