Q:

Does inside "if" statement change running time of algorithm?

I have written the running time based on my calculation in red color on the picture. But I don't know what would be for that IF statement as well as it's body's running time. Will that IF condition's running time would be n x n ? Because each time in the inner loop, it would be evaluated. Isn't it? What about it's body's?

A:

You need to take into account two different parameters, m and n. The outermost loop executes m times, and the inner loop executes n times. The complexity, therefore, is θ(mn).
Note that the if-statement and its body are executed in constant time.

