# W1 Notes: Time Complexity + STL 1

## Time Complexity Analysis; Big-O Notation

To measure the performance of algorithms, we use the asymptotic notation of mathematics --- the [Big-O notation](https://en.wikipedia.org/wiki/Big_O_notation). The *time complexity* of an algorithm

Watch this: [Data Structures 001: Tradeoffs and Big-O - YouTube](https://www.youtube.com/watch?v=uXqe1g5O2fM&list=PLJnkyVAO-LM7gy3qLnukI0cUq8difbMm3&ab_channel=TimothyJames)

### 1.1 $O(n)$ Examples

#### 1.1.1

for (int i = 0; i < n; ++i) {
    // do something
}

#### 1.1.2

for (int i = 0; i < n; i += 2) { // O(n / 2) ~ O(n)
    // do something
}

#### 1.1.3

for (int i = 0; i < 100 * n; ++i) { // O(100 * n) ~ O(n)
    // do something
}

#### 1.1.4

for (int i = 0; i < 1000 * n; ++i) { // O(100 * n) ~ O(n)
    // do something
}

## Implementation and Data Structures 1

### C++

### `std::string`

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

int main() {

    // Constructors | O(length of constructed string)
    // https://www.cplusplus.com/reference/string/string/string/
    string s1; // default
    string s2("abc"); // from C-style string
    string s3(10, 'x'); // fill
    string s4(s3.begin(), s3.end()); // range

    // `=` operator overloads; assigns new content | O(length of assigned content)
    // https://www.cplusplus.com/reference/string/string/operator=/
    s1 = s2; // s1 becomes "abc"
    s2 = "xyz"; // s2 becomes "xyz"

    // Assigns new content | O(length of assigned content)
    // https://www.cplusplus.com/reference/string/string/assign/
    s1.assign(s2);
    s2.assign("xyz");
    s3.assign(15, 'c');

    // Returns length | O(1)
    // https://www.cplusplus.com/reference/string/string/s  ize/
    int len = s1.size();

    // Returns length | O(1)
    // https://www.cplusplus.com/reference/string/string/length/
    len = s2.length();
    
    // Checks if size == 0 | O(1)
    // https://www.cplusplus.com/reference/string/string/empty/
    bool isempty = s1.empty();

    // Resizes (grows or shrinks) | O(length added/erased content)
    // https://www.cplusplus.com/reference/string/string/resize/
    s1.resize(15, 'c');

    // `[]` operator overloads; returns read/write access at the specified index | O(1)
    // https://www.cplusplus.com/reference/string/string/operator[]/
    s1[0] = s2[s2.size() - 1];
    s2[0] = 'a';

    // `+=` operator overloads; appends content | O(length of appended content)
    // https://www.cplusplus.com/reference/string/string/operator+=/
    s1 += s2;
    s2 += 'c';
    s3 += "ssss";

    // `+` operator overloads; contatenates | O(length of resulting string)
    // https://www.cplusplus.com/reference/string/string/operator+/
    string temp1 = s1 + s2;
    string temp2 = s2 + 'c';
    string temp3 = s3 + "ssss";

    // Erases last character | O(1)
    // https://www.cplusplus.com/reference/string/string/pop_back/
    s1 = "abc";
    s1.pop_back(); // now s1 == "ab";

    // Clears
    // https://www.cplusplus.com/reference/string/string/clear/
    s1.clear(); // now s1 == ""

    // Relational operator overloads; based on lexicographical ordering of content | O(1)
    // https://www.cplusplus.com/reference/string/string/operators/
    bool b1 = s1 == s2;
    bool b2 = s1 != s2;
    bool b3 = s1 < s2;
    bool b4 = s1 <= s2;
    bool b5 = s1 > s2;
    bool b6 = s1 >= s2;

    return 0;
}