I am kind of new to running time and so I am trying to basic examples.

Take the following function as example and I will show my attempt to compute its running time. The function below refers to a BinarySearchTree where 'u.e.' represents the left child of 'u' and 'u.d' represents the right child of 'u'. Additionaly, 'u.p' represents the parent of 'u' and 'self.r' represents the root of our binary search tree. I believe this isn't important to my question but it's just to give some context.

     function                           |       cost      |       times (run)
                                        |                 | 
def splice(self,u):                     |                 |
    if u.e is not None: w = u.e         |        c1       |           1          
    else: w = u.d                       |        c2       |           1
    if u == self.r:                     |                 |
        self.r = w                      |        c3       |           1
        p = None                        |        c4       |           1
    else:                               |                 |
        p = u.p                         |        c5       |           1       
        if p.e == u: p.e = w            |        c6       |           1 
        else: p.d = w                   |        c7       |           1 
    if w is not None: w.p = p           |        c8       |           1

In this example, I believe it won't matter considering the worst case scenario (since the run time will be equal (or almost equal)). Altought, let's imagine it:

The worst case will be when we enter the second else statement and when we also enter the last if statement. The first if-else statements are basically equal and so it doesn't matter which one we enter. So, the worst case running time will be obtained by:

T(n) = c1 c5 c6 c8 = c, for some constant c

Is this correct? And does this mean that the time complexity of this algorithm is O(1) ? I.e., constant time?

CodePudding user response：

That is right, it's O(1), however when we analyse time complexity we rather focus on every line, as every single basic operation is constant. We ask more about how many times ths lines are executed:

def foo(n):
    for i in range(n):
        if 1:
            ...
        if 2:
            ...
        if 3:
            ...
        # no matter how many ifs are there

We run loop n times, so complexity would be (assuming ifs body has basic operations) O(n). If you have two nested loops, it would be O(n*m) where n, m are number of iterations of this loops. Unfortunately it's not always so simple and becomes more tricky e.g. in recursive function. I recommend you to read this article to get more insight into O notation.

CodePudding user response：

Yes. In general, if you have no loops of indefinite size occurring in a function, the run time will be O(1).

A function will exceed O(1) if some parts of your code are executing multiple times depending on the size of your input, 'n'.