How to find the cost of pseudocode with a nested loop and a nested if statement?

Problem Detail: 

How can I find the cost of pseudocode with a nested loop and a nested if statement?

On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I found. I took a guess, but I don't know what the time would be for the inner code fragments.

I am especially unsure what the code segments inside the if statement would be because the if statement doesn't always occur.

Asked By : user14864

Answered By : SeeMoreGain

Big O analysis

The answer is O(n^2).

Good strategy for working this out is eliminate all constant time operations (unless it is a return / break that will change the loop), as everything will always be at least O(1).

This means you can eliminate everything inside the if, as well as the if. So you are left with a simple nested loop running over n

Hence O(n^2)

Cost analysis

You always assume worst case (unless explicitly told otherwise). Therefore assume if statement will be true and statements will run every loop (as there can exist a sorting order where this is true), so your statements will have the same cost as your loop

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21829