CODEWITHSUNDEEP
runtimeasymptotic-complexity
tealove12
tealove12

Reputation: 25

Runtime of this Program

I'm currently in an Intro to Java course and studying for a midterm. I came across this problem:

public void wug() {
    int j = 0;
    for (int i = 0; i < N; i += 1) {
        for (; j < M; j += 1) {
            if (bump(i, j))
                break;
        }
    }
}

N and M are trivial, and are provided somewhere else.

The solution says the runtime if theta(M+N) for the worst case, and theta(N) for the best case. I understand the best case, but I thought the worst case was theta(N*M). Could someone explain why the worst case is theta(M+N)? I'm really shaky on algorithm complexity. Thank you!

Upvotes: 0

Views: 135

Answers (2)

christutty
christutty

Reputation: 952

Note that j isn't initialised in the inner loop so each execution of the inner loop continues from where the previous loop exited. Think through how that changes the different values that j takes as the program executes.

You'll gain better understanding of this code by setting it up in a debugger and single-stepping through it. That's because you're seeing what you think the code is doing, not what's actually happening. Single-stepping the code helps you to focus on the details that make the difference.

Upvotes: 0

JJJ
JJJ

Reputation: 33163

Note that j is never reset, so the inner loop iterates at most M times. To get N*M iterations you'd have to reset the iterator to zero at the start of the loop.

Upvotes: 1

Related Questions