Finding the worse-case runtime of a function

Question

I seriously do not understand where to go with the following question.

Any hints or steps would be greatly appreciated.

I really want to know what I'm supposed to do, as opposed to just getting the answers.

I understand why we use Big-Oh (Worst-case) but I can't wrap my mind behind the mathematics. How to you calculate the total runtime?

Count, starting from the inner for loop, how many times each loop executes the operations inside it. What do you get? — IVlad, Jan 16 '17 at 20:16
You don't have any *worst* or *best* cases in the context. The sum of operations itself (let's assume the inmost loop as one operation) is equal to `n * (n + 1) * (2 * n + 1) / 6 == O(n**3)`. — Dmitry Bychenko, Jan 16 '17 at 20:21
@IVlad How do you count them if you have so many unknowns? _j:=i+1_ would be considered what? — killmepls3, Jan 16 '17 at 20:27
@IVlad If _i_'s max value is _n-1_, then _j_ would be _(n-1)+1_ = _n_, which means it is only incremented once? That wouldn't make any sense though. I'm really lost as to how to approach this. — killmepls3, Jan 16 '17 at 20:33
How many times does `j` get incremented in terms of `n` and `i`? — IVlad, Jan 16 '17 at 20:34
Yes. So, the second `for` executes the third `n-1 + n-2 + ... + 1` times. How many times does the third `for` execute its body in terms of `j`? — IVlad, Jan 16 '17 at 20:45
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Jan 16 '17 at 20:55
Right. Now, for each of `j` iterating `n-1`, `n-2`, ..., `1` times, how many times will `k` iterate? Sum those, and you have the running time of the two inner loops. — IVlad, Jan 16 '17 at 20:57
@IVlad Would `k` iterate `j + (n-i) + (n-1)` times? I pulled `j` from the number of times the third loop ran, `(n-i)` from the number of times the second loop ran, and `(n-1)` from the number of times the first loop ran. — killmepls3, Jan 16 '17 at 21:02
Ignore the first loop, so there is no `i`. You have the second running `n-1`. How many times will the third run? Then you have the second running `n-1`, how many times will the third run? Etc. until the second running `1`, how many times will the third run? Sum all these, what do you get? — IVlad, Jan 16 '17 at 21:06
@IVlad I'm a bit confused, but I think it'd be `j+(n-1)`, where `j` stems from the third loop, and `(n-1)` stems from the number of times the second loop runs. — killmepls3, Jan 16 '17 at 21:10
You can't have `j` anymore either, it must be fully in terms of `n`. — IVlad, Jan 16 '17 at 21:11
@IVlad I can't really wrap my head around this. Could you give me a little hint? — killmepls3, Jan 16 '17 at 21:23
`j = 2 => k iterates 2`, `j = 3 => 3, j = 4 => 4, ..., j = n => n`. `2 + 3 + 4 + ... + n = O(n^2)`. This is when `i = 1`. Now what happens when you consider the first for loop again? — IVlad, Jan 16 '17 at 21:28
@IVlad Kinda a guess, but would it be `n^2 * (n-1)` = `n^3 - n^2`? — killmepls3, Jan 16 '17 at 21:37
Looks about right. You don't have to be exact, just have to find the dominating term. If you've found `n^3`, then the whole thing is `O(n^3)`. — IVlad, Jan 16 '17 at 21:38

Vinayak Singla · Answer 1 · 2017-01-20T19:28:14.843

To calculate Big-Oh notation you need to find the worst case running time. We do this for three loops

1) i varies from 1 to n-1  so total times the loop runs n-1=O(n)
2) j goes from 2 to n,3 to n..............n-1 to n so here total times the loop runs (n-2)+(n-3).......+1=(n-1)(n-2)/2=O(n^2)
3) now for each  value of j say a. k goes from 1 to a . This will add up another O(n) for each loop.(as value of a can go upto n)

Conclusion
Total loops of j O(n^2) and inside each loop we have O(n) operation.
Therefore O((n^2)*n)=O(n^3)

Hope i was able to explain how we get Big-Oh notation

Finding the worse-case runtime of a function

1 Answers1