logo

UTK Notes


Clicker Questions - 11-A-Big-O

For each of the following procedures, enter the big-O of its running times. Please represent v’s size as $m$, and express your big-O as a function of $n$ and $m$.

Question 1:



1
2
3
4
5
6
7
8
9
10



#include <vector> 
using namespace std;

void a(vector <int> &v, int n)
{
    int i;
    for (i = 0; i < n; it+) {
        v. push_back(i*i);
    }
}
Answer push_back() is $O(1)$ and the loop iterates $n$ times, so the answer is $O(n)$.

Question 2:



1
2
3
4
5
6
7
8
9
10
11
12
13



#include < vector>
#include "nlohmann/json.hpp"
using namespace std; 
using nlohmann:: json;

string vtojs(vector <string> &V)
{
    json ji
    size_t i;

    for (i= 0; i < v.size(); i++) jlvlill=i;
    return j.dump(2);
}

Please assume that all of the strings in $v$ are less than 10 characters.

Answer Recall, JSON objects are implemented with maps. This is why they are sorted when you print of dump() them. Thereforce, this is $O(m \; log \; m)$.

Question 3:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15



#include <vector>
#include < set>
#include <iostream> 
using namespace std;

bool b(vector < int> &v, int n)
{
    multiset < int> s;
    int i;

    for (i = 0; i < v.size(); i++) {
        s.insert (v[i]);
    }
    return (s.find(n) != s.end());
}
Answer The loop iterates $m$ times, and the insert() operation on average is $O(log \; m)$. The last find() is $O(log \; m)$, so it may be ignored. The answer is $O(m \; log \; m)$.

Question 4:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23



#include <vector>
#include <iostream> 
using namespace std;

int find(vector < int> &v, int n)
{
    int l, h, m;

    l = 0; 
    h = v.size();

    while (1 < h) {
        m = (1th) /2;
        if (m == h) m--;
        if (v[m] == n) return m;
        if (v[m] > n) {
            h = m;
        } else {
            1 = m+1;
        }
    }
    return l;
}
Answer The variable $m$ is set to the midpoint between $l$ and $h$. Thus $(h-1)$ is reduced by half at each iteration. $(h-l)$ starts at $m$, so this loop iterates $O(log \; m)$ times. The answer is $O(log \; m)$.

PDF Download, No 2022 Class Stats, 2023 Class Stats