I have this algorithm

Algorithm (A[1..n])
    for i <- 1 to n do
        if (A[i] < 0) then
            A[i] <- 1 * A[i]
        End if
    End for

I have to find the total number of assignment in the worst case, but I'm a little bit confused, do I say I have 2 or 1, one for the assign A[i] in the statement and second for the i in the for loop (i <- 1).

up vote 1 down vote accepted

Likely the question is asking you to focus on line 4, in which you assign a value to A[i]. You can also focus on the for-loop with and its control variable to get a complete answer, but the only way to know for sure is to ask the person responsible for the problem.

Anyway, more precisely, the question is how many assignments do you do in the worst case as a function of the array length $n$. As you can see, this number is determined by the number of times the preceding if-branch evaluates to true. Your task is to argue how many times that can happen in the worst case.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.