Step-wise analysis practice problems

I’ve had some requests for some step-wise analysis practice problems, so here they are. In all these problems, you should count only the operations that occur directly within the given function. For example, if you are asked to count v[...] (vector subscripts) and the function contains a call to v.erase(...), while it is correct to assume that the implementation of erase relies on [...] internally, you should not try to count how many times erase uses [...] and include that in your total. Just count the direct uses of [...] (or whatever) by the function itself.

int sum(int n)
{
    int s = 0;
    for(int i = 0; i <= n; ++i)
        s = s + i;
    return s;
}

Count the number of s = ... (assignments to s). Can you improve this number?

int sum(int low, int high)
{
    int s = 0;
    for(int i = low; i <= high; ++i)
        s = s + i;
    return s;
}

Count the number of s = ... (assignments to s).

float avg(const vector<int>& v)
{
    float s = 0.0;
    for(size_t i = 0; i < v.size(); ++i)
        s = s + v[i];

    s = s / v.size();
    return s;
}

Count the number of calls to v.size(), the number of v[...] (vector subscripts), and the number of s = ... (assignments to s).

float stddev(const vector<int>& v)
{
    // Compute average
    float s = 0.0;
    for(size_t i = 0; i < v.size(); ++i)
        s = s + v[i];

    s = s / v.size();

    // Compute stddev
    float d = 0.0;
    for(size_t i = 0; i < v.size(); ++i)
        d = d + (v[i] - s) * (v[i] - s);

    d = d / v.size();
    d = sqrt(d);

    return d;
}

Count the number of calls to v.size(), the number of v[...] (vector subscripts), the number of s = ... (assignments to s), and the number of d = ... (assignments to d).

bool min(const vector<int>& v)
{
    assert(v.size() > 0);

    int m = v[0];
    for(size_t i = 1; i < v.size(); ++i)
        if(v[i] < m)
            m = v[i];

    return m;
}

Count the number of v[...] (vector subscripts) and the number of m = ... (assignments to m) in the best and worst cases.

void minmax(const vector<int>& v, int& low, int& high)
{
    assert(v.size() > 0);

    low = v[0];
    high = v[0];

    for(size_t i = 1; i < v.size(); ++i) {
        if(v[i] < low)
            low = v[i];
        if(v[i] > high)
            high = v[i];
    }

}

Count the number of v[...] (vector subscripts), the number of v[i] > ... or v[i] < ... (comparisons of vector elements), the number of low = ... (assignments to low) and the number of high = ... (assignments to high), in the best and worst cases.

Hint: other than v[0], is it possible for any other element of the vector to be both the largest, and the smallest, at the same time?

Bonus: Figure out how to reduce the number of comparisons in the worst case.

bool is_sorted(const vector<int>& v)
{
    bool sorted = true;
    for(size_t i = 0; i+1 < v.size(); ++i)
        if(v[i] > v[i+1])
            sorted = false;

    return sorted;
}

Count the number of v[...] vector subscripts, the number of v[...] > v[...] (comparisons of vector elements; do not count the loop variable comparison), and the number of sorted = ... (assignments to the sorted variable, in the best and worst cases.

bool is_sorted(const vector<int>& v)
{
    for(size_t i = 0; i+1 < v.size(); ++i)
        if(v[i] > v[i+1])
            return false;

    return true;
}

Count the number of v[...] vector subscripts and the number of v[...] > v[...] (comparisons of vector elements; do not count the loop variable comparison) in the best and worst cases.

bool is_palindrome(const vector<int>& v)
{
    if(v.empty() or v.size() == 1)
        return true;

    for(size_t i = 0, j = v.size()-1; i < j; ++i, --j)
        if(v[i] != v[j])
            return false;

    return true;
}

Count the number of calls to v.size(), and the number of v[i] != v[j] inequality comparisons of vector elements, in both the best and worst cases. (Consider both the cases when the size is even, and when the size is odd.)

bool in_range(const vector<int>& v)
{
    for(size_t i = 1; i+1 < v.size(); ++i)
        if(v[i] < v[0] or v[i] > v[v.size()-1])
            return false;
    return true;
}

Count the number of v[...] vector subscripts, the number of calls to v.size(), and the number of v[...] > v[...] (comparisons of vector elements; do not count the loop variable comparison) in the best and worst cases.

void remove_duplicates(vector<int>& v)
{
    for(size_t i = 0; i < v.size(); ++i) {
        // Remove duplicates of v[i] in the remainder of the vector
        for(size_t j = i + 1; j < v.size(); ++j)
            // Found a duplicate, shift down
            if(v[j] == v[i]) {
                for(size_t k = j; k+1 < v.size(); ++k)
                    v[k] = v[k+1];
                v.pop_back();
            }
    }

Count the number of v[...] (vector subscripts) and v.pop_back() calls, in both the best and worst cases. 

vector<int> duplicates_removed(const vector<int>& v)
{
    vector<int> result;
    for(size_t i = 0; i < v.size(); ++i) {
        // Determine if v[i] is already in result
        bool exists = false;
        for(size_t j = 0; j < result.size(); ++j)
            if(result[j] == v[i]) {
                exists = true;
                break;
            }

        if(not exists)
            result.push_back(v[i]);
    }

    return result;
}

Count the number of v[...] or result[...] (vector subscripts), and the number of result[...] == v[...] equality comparisons of vector elements, and the number of result.push_back(...) push-back operations.

void selection_sort(vector<int>& v)
{
    for(size_t i = 0; i+1 < v.size(); ++i) {
        // Find smallest in v[i] ... end
        size_t smallest = i;
        for(size_t j = i+1; j < v.size(); ++i)
            if(v[smallest] < v[i])
                smallest = i;

        swap(v[i], v[smallest]);
    }
}

Count the number of v[...] vector subscripts, the number of v[...] < v[...] comparisons of vector elements, and the number of swap(...) calls to the swap function. Can any of these be reduced?