Counting valleys from a sequence of steps where each step is either 'U' or 'D'. What is the time complexity of this solution?

Given a sequence of up and down steps. Find and return the number of valleys in the given sequence. The sequence always starts and ends at the sea level, and each step up or down represent one unit change in altitude.

• A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level
• A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Example: If the path is 'DDUUUUDD', first we enter a valley two units deep.Then we climb onto a mountain two units high.Finally we return to the sea level. Therefore we return one.

Question: Is the time complexity of the given solution O(n / 2) or O(n), and how does an if statement change the complexity of an algorithm ?

Solution:

def countingValleys(n, s):

altitude = 0
prev_a = 0
v_count = 0

for i in range(1, n, 2):
    if s[i] == s[i-1]:
        if s[i] == 'D':
            altitude -= 2
            prev_a = altitude + 1
        else:
            altitude += 2
            prev_a = altitude - 1
    else:
        if s[i] == 'D':
            prev_a = altitude + 1
        else:
            prev_a = altitude - 1

    if altitude == 0 and prev_a == -1:
        v_count += 1

return v_count