0

I'm having trouble with finding the O-time of some algoritms. I've searched quite some O notations but whenever my excercise gets harder, I can't find the solution. Now I came across an algoritm and I can't really find a solution. I've searched through Stack Overflow but found nothing to really help me. The best post I found was this. It only said what I knew and not really how to calculate it or see it. Also the second post did say some algoritms with solutions, but not how to find it.

The Code

`for i = 1; i <= n; i++
    for j = 1; j <= i; j++
        for k = 1; k <= i; k++
            x = x + 1
`

Question

What is the time complexity of this algorithm?

Also, are there some good tutorials to help me understand this matter better?

Also sorry if there's a stack overflow post of this allready but I couldn't find a good one to help me.

Community
  • 1
  • 1
Stan Fieuws
  • 162
  • 1
  • 2
  • 13

1 Answers1

2
  • The loop defining i runs n times.
  • The loop defining j runs n * n/2 times
  • The loop defining k runs n * n/2 * n/2 times

= n * 1/2 * n * 1/2 * n

= n * n * n * 1/2 * 1/2

= O(n^3)

You can also try to infer that from the final value of the variable x, which should be roughly proportional to n^3

arboreal84
  • 2,086
  • 18
  • 21