Computing the running time of a given function in Python

Question

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?

kosciej16 · Accepted Answer · 2022-04-08 22:34:02Z

2

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.

answered Apr 8, 2022 at 22:34

kosciej16

7,2783 gold badges21 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Rodrigo Over a year ago

Thanks for your help! What I meant by the 'times' column is the times each line was executed and I did it for every line so it is clear for my classmates, since we're all new into this

Xela · Accepted Answer · 2022-04-08 22:31:30Z

1

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'.

answered Apr 8, 2022 at 22:31

Xela

1191 silver badge10 bronze badges

Collectives™ on Stack Overflow

Computing the running time of a given function in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related