What is the time complexity of this algortma?

Question

x=0
for i=1 to ceiling(log(n))
    for j=1 to i
        for k=1 to 10
            x=x+1

I included the answer I provided here:

I believe the time complexity is θ (n ^ 2 log (n)), but I'm not sure my logic is correct. I would really appreciate any help in understanding how to do this type of analysis!

Answer 1

The extreme loop will run for times. The average cycle depends on the value . ceil(log n)i

So this will be:

1st iteration of outermost-loop    - 1
2nd iteration of outermost-loop    - 2
.....................................
ceil(log n) iteration of outermost-loop     - ceil(log n)

The inner loop is independent of other variables, and will always be executed 10once for each iteration of the middle loop.

Hence network iterations

= [1*10 + 2*10 + 3*10 + ... + ceil(log n)*10] 
= 10 * {1+2+...+ceil(log n)}
= 10 * { (ceil(log n) * ceil(log n)+1)/2} times
= 5 * [ceil(log n)]^2 + 5 * ceil(log n)
= Big-Theta {(log n)^2}
= Θ{(log n)^2}.

Hope this is clear to you. Therefore, your answer is incorrect.

Answer 2

. .

: n i 10 . , Theta(10).

: Theta(logn).

: i logn, O(logn)

: Theta(logn)*O(logn)*Theta(10) O(logn*logn*10) 10*O((logn)^2) O((logn)^2)