0

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

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

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.

Votes + Comments
Way better than Rashakil Fol... ;-)
ur da man, Dashakil
A very competent new member.
Very knowledgable new poster... ;P
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.