Example showing growth of O(n) search. See video at https://youtu.be/PB4wHHS_f3A

helpers.h

#include <iostream>
#include <iterator>
#include <random>
#include <chrono>

using namespace std;

#ifndef LSEARCH_UTILS_H
#define LSEARCH_UTILS_H

// seed the random number generator
std::mt19937 gen(chrono::high_resolution_clock::
                 now().time_since_epoch().count());

/**
 * Returns a random number between low (inclusive) and high (inclusive)
 * Based on http://stackoverflow.com/a/19036349, last access 10/4/2016
 *
 * @param low the low end of the range (inclusive)
 * @param high the high end of the range (inclusive)
 * @return a random number between low (inclusive) and high (inclusive)
 */
int rand_in(int low, int high) {
    return std::uniform_int_distribution<int>{low, high}(gen);
}

template<typename T>
ostream& operator<<(ostream& ostr, const vector<T>& v) {
    ostr << "{ ";
    copy(begin(v), end(v) - 1, ostream_iterator<T>(ostr, ", "));
    ostr << v.at(v.size() - 1);
    ostr << " }";
    return ostr;
}

#endif //LSEARCH_UTILS_H

main.cpp

#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include "helpers.h"  // defines rand_in

using namespace std;

const int min_num = 1;
const int max_num = 100;

/**
 * Searches an (unsorted) vector for the specified number.
 * @param nums the vector to search.
 * @param target the number we are searching for.
 * @return the index of target in nums.  If target is not
 *         found, then -1
 */
int search(const vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums.at(i) == target) {
            // found it!
            return i;
        }
    }
    // not found!
    return -1;
}

/**
 * Times how long (in milliseconds) it will take to
 * search for a number that is not in nums.
 * @param nums the vector to search.
 * @return how long (in milliseconds) it will take to
 *         search for a number that is not in nums.
 */
auto timed_search(const vector<int>& nums) {
    // get the current time
    auto start = chrono::system_clock::now();
    // search for a number not in nums
    search(nums, rand_in(max_num + 1, INT_MAX));
    auto stop = chrono::system_clock::now();
    auto diff = stop - start;
    return chrono::duration<double, milli> (diff).count();
}

/**
 * Returns the average time (in milliseconds) that it takes to
 * search the given vector for a number that is not in it.
 * @param nums the vector to search.
 * @param num_trials the number of trials.
 * @return the average time (in milliseconds) that it takes to
 *         search the given vector for a number that is not in it.
 */
double avg_timed_search(const vector<int>& nums, int num_trials = 10) {
    auto sum = 0;
    for (int i = 0; i < num_trials; i++) {
        sum += timed_search(nums);
    }
    return sum / static_cast<double>(num_trials);
}

int main() {
    int nums_size = 100000;

    // create a parameterless random function that returns
    // a number between min_num (inclusive) and max_num (inclusive)
    auto rand_fn = bind(rand_in, min_num, max_num);

    // output headers
    cout << setw(8) << left << "n";
    cout << "\ttime" << endl;

    for (int i = 0; i < 9; i++, nums_size = nums_size * 2) {
        // create a vector of size nums_size with random numbers
        // in the range from min_num to max_num
        vector<int> nums(nums_size);
        generate(begin(nums), end(nums), rand_fn);

        auto time_ms = avg_timed_search(nums, 50);

        cout << setw(8) << left << nums_size << "\t";
        cout << setprecision(1) << fixed
             << time_ms << "ms" << endl;
    }


}