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.
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
