CODEWITHSUNDEEP
pythonalgorithmbig-o
calccrypto
calccrypto

Reputation: 131

time complexity of variable loops

i want to try to calculate the O(n) of my program (in python). there are two problems:

1: i have a very basic knowledge of O(n) [aka: i know O(n) has to do with time and calculations]

and

2: all of the loops in my program are not set to any particular value. they are based on the input data.

Upvotes: 1

Views: 1019

Answers (2)

Travis Bradshaw
Travis Bradshaw

Reputation: 4320

Try this out to start, then head to wiki:

Upvotes: 1

pavpanchekha
pavpanchekha

Reputation: 2093

The n in O(n) means precisely the input size. So, if I have this code:

def findmax(l):
    maybemax = 0
    for i in l:
        if i > maybemax:
            maybemax = i
    return maybemax

Then I'd say that the complexity is O(n) -- how long it takes is proportional to the input size (since the loop loops as many times as the length of l).

If I had

def allbigger(l, m):
    for el in l:
        for el2 in m:
            if el < el2:
                return False
    return True

then, in the worst case (that is, when I return True), I have one loop of length len(l) and inside it, one of length len(m), so I say that it's O(l * m) or O(n^2) if the lists are expected to be about the same length.

Upvotes: 4

Related Questions