Originally Posted by Rashakil Fol

Count the total number of fundamental operations the algorithm performs, relative to some value N. For example, this function..

Help with Code Tags

(Toggle Plain Text)

int factorial(int n) {
    int ret = 1;
    while (n != 0) {
        ret *= n;
        -- n;
    }
    return ret;
}

int factorial(int n) { int ret = 1; while (n != 0) { ret *= n; -- n; } return ret; }

The function sets the value of ret to 1. This is one operation.

Then this function tests the condition of the while loop exactly 1 + n times. It runs the body of the while loop exactly n times. The body of the while loop performs exactly 2 fundamental operations: 'multiply ret by n', and 'decrement n'. The condition has one fundamental operation, comparison. Calling the function counts as a fundamental operation, too.

So we have the total number of fundamental operations being
1 + 1 + (1 + n) + 2 * n. (The sum is composed of the operations for calling the function, setting ret = 1, performing a total of 1 + n tests in the condition of the while loop, and a total of 2 * n operations in the body of the while loop.)

This simplifies to 3 + 3 * n fundamental operations, which is O(n).

(What do I mean by 'fundamental operation'? Any operation that takes an amount of time that is bounded by a constant.)