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

3
Contributors
2
Replies
3
Views
8 Years
Discussion Span
Last Post by kaleesh.warrior

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.