Definition

“Time complexity is the measure of how an algorithm's runtime scales with input size, often expressed using Big-O notation, which provides an upper bound on the worst-case scenario”

— https://www.datacamp.com/tutorial/big-o-notation-time-complexity —

The Big O notation’s formal definition is actually more precise then the widely used definition which is considered more practical.

Simply put:

• in formal definition, Big-O is defined mathematically to describe the upper bound of a function's growth rate
• in computer science, Big-O is used more intuitively to describe the dominant factor of an algorithm's running time or space requirement as input size (n) grows It abstracts away constants and lower-order terms to focus on scalability

Here is the link to the formal definition if you are interested: https://web.mit.edu/16.070/www/lecture/big_o.pdf

Examples

Example 1: Sum of a List

Consider this Python function that calculates the sum of all elements in a list:

def calculate_sum(arr):

    total = 0
    for num in arr:
        total += num
    return total

Time Complexity Analysis: