Learn DSA with Me ( Day 1 )

Time Complexity (Big O)

Today I will be beginning a series of posts called "Learn DSA with Me". This will follow my journey into data structures and algorithms. I will be writing what I learn everyday on this post in a summarized form.

Today I learnt the first and most basic concept in DS & A, understanding time complexity.
Time complexity is how long it takes for an algorithm to execute, and it's based on the size of the input.
Time complexity is expressed in what's called Big O notation.
Let me give you some examples:

Example 1 - Time Complexity O(1)

int main(){
    //Time complexity of O(1) since it will be called 1 time.
    cout >> "Hello World" >> endl;
}

Example 2 - Time Complexity O(n)

int main(){
    int n;
    cin >> n;
    //Time complexity of O(n) since it will be called n times.
    for(int i = 0; i<n; i++){
        cout >> "Hello World" >> endl;
    }
}

Example 3 - Time Complexity O(n²)

int main(){
    int n;
    cin >> n;
    //Time complexity of O(n²) since it will be called n² times.
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            cout >> "Hello World" >> endl;
        }
    }
}

How To Analyze Time Complexity

Now I am going to teach you how to analyse these time complexities. So here we go!.

int main(){
    int n;
    cin >> n;
    //Time complexity of O(n²) since it will be called n² times.
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            cout >> "Hello World" >> endl;
        }
    }
}

Looking at the third example again, looking at the program we can deduce how many times each statement is going to be executed.

int main(){
    int n; -------------------------------- 1 times
    cin >> n; ----------------------------- 1 times

    for(int i = 0; i<n; i++){
        Statements... --------------------- n times
        for(int j = 0; j<n; j++){
            cout >> "Hello World" >> endl;- n² times
        }
    }
}

Adding them all up we get a polynomial f(n) = 1+1+n+n² = 2+n+n². The degree of f(n) determines the time complexity. The degree is the highest power of n in f(n). So, in f(n), the highest power is n², therefore the time complexity is O(n²).

Hoping everyone enjoyed the article, the next one will be published in 2-3 days, so lookout for that. Till then, bye!