Please can anyone tell me how to calculate time complexity of following algorithm in terms of big theta
l=0
for i=1 to n do
for j=1 to (n*n) do
for k=1 to (n*n*n) do
l=l+1
thanks in advance
Please can anyone tell me how to calculate time complexity of following algorithm in terms of big theta
l=0
for i=1 to n do
for j=1 to (n*n) do
for k=1 to (n*n*n) do
l=l+1
thanks in advance
Count the number of steps it takes. The stuff that makes the for loops run takes a constant amount of time through each iteration so you only need to count how many iterations happen. There are n outer iterations, and n*n middle iterations per outer iteration, and n*n*n inner iterations per middle iteration, so the total number of middle iterations is n*(n*n) and thus the total number of inner iterations is (n*(n*n))*(n*n*n), i.e. n^6. The cost of the overhead of running each middle and outer iteration still exists, and they have O(n) and O(n*(n*n)) i.e. O(n^3) cost, respectively. The inner iteration's cost as already mentioned is O(n^6), so the total amount of time can be represented as O(n) + O(n^3) + O(n^6) -- but that equals O(n^6) by the way one can simplify the sum of O notations.
Actually, I suppose the line l = 0 has an O(1) cost, so the expression would be O(1) + O(n) + O(n^3) + O(n^6), but that doesn't change the answer. Little constant time costs never change the answer.
yo :D. Actually there's another excellent thread herehttp://www.daniweb.com/forums/showthread.php?t=13488
the first two pages are full of info. I'm trying to learn this thing as well :s.. not so clear cut.