Big-O Notation of a for-loop with an conditional inner loop-CodePudding

I am trying to understand the time complexity of this program, and why. I've made some notes of what I think it is, but I'm unsure if I understood it correct.

 public static int countSteps(int n) {
    int pow = 2;                             // O(1)
    int steps = 0;                           // O(1)
    for (int i = 0; i < n; i  ) {            // O(n)
        if (i == pow) {                      // O(1)
            pow *= 2;                        // O(1)
            for (int j = 0; j < n; j  ) {    // O(n)
                steps  ;                     // O(1)
            }
        }
        else {
            steps  ;                         // O(1)
        }
    }
    return steps; // O(1)
}

The inner loop spends a lot of time iterating through n every time the if-statement is triggered, does that affect the time complexity or is it still constant?

CodePudding user response：

The outer loop means it's at least O(n). The inner loop will run only when i is a power of two, so it's O(n*log n).