algorithm - How to calculate the complexity of a "not so simple" program? -

algorithm - How to calculate the complexity of a "not so simple" program? -

i know how calculate complexity of programme whenever there variable declaration or simple loops involved (i.e linear case ) counting number of times each line executed.

but in cases see lines of code run logarithmically,exponentially,in cubic order,etc, want know how can figure out?

the [following][3] figure dices analysis of runtime of merge sort algorithm: split original array 2 arrays of size n / 2 each. merge arrays, operation merges n elements , takes Θ( n ) time. argument, complexity each row Θ( n ). know number of rows in diagram, called depth of recursion tree, log( n ). reasoning same 1 used when analyzing complexity of binary search. have log( n ) rows , each of them Θ( n ), hence complexity of mergesort Θ( n * log( n ) )

simple programs can analyzed counting nested loops of program. single loop on n items yields f( n ) = n. loop within loop yields f( n ) = n2. loop within loop within loop yields f( n ) = n3.

given series of loops sequential, slowest of them determines asymptotic behavior of program. 2 nested loops followed single loop asymptotically same nested loops alone, because nested loops dominate simple loop.

:= 1; while ( < n ) = * 2;

the running time logarithmic, o(logn) because of multiplication 2.

few useful links are: http://cs.stackexchange.com/questions/192/how-to-come-up-with-the-runtime-of-algorithms

i hope help you!

algorithm asymptotic-complexity