CODEWITHSUNDEEP
pythonfunctiontime-complexitybig-o
Gazza732
Gazza732

Reputation: 179

How does Big O notation work?

Ok so I'm fairly new to coding and I am to approximate a WCET T(a, b) and complexity of a function. Example function:

def testFunction(self):
    x = 0
    for r in range(a):
        for c in range(b):
            if testFunction2(r, c):
                x = x + 1
return x

I understand that the complexity of this function is quadratic O(N^2) but I'm not sure on approximating the WCET?

Also isn't there only two assignments in that function, being:

x = 0

and

x = x + 1

? If so, how do I express the assignments with T(a, b)?

Maths has never been my strong point but I want to learn how to do this. None of the materials I've read explains it in a way I understand.

Thanks in advance.

Upvotes: 1

Views: 117

Answers (2)

metmirr
metmirr

Reputation: 4312

def testFunction(self):
    x = 0                               # 1
    for r in range(a):                  # a
        for c in range(b):              # b
            if testFunction2(r, c):     # a*b
                x = x + 1               # depends testFunction2
    return x                            # 1

WCET for this function ab where a=n b=n then you can say O(n^2) if always testFunction2 returns True then x = x +1 will execute ab times but it wont effect the sum of execution time. Finally you sum all this exection time:

(1 + a + b + a*b + a*b + 1)
2 + a + b + 2*a*b

for example, while n = 1000 and a=b=n

2 + 1000 + 1000 + 2*1000*1000
2002 + 2000000

so when you evalute this result you will see 2002 is nothing while you have 2000000.

Upvotes: 1

Caleth
Caleth

Reputation: 63162

For a Worst Case Execution Time, you can simply assume there is an input specifically crafted to make your program slow. In this case that would be testfunction2 always returns true.

Within the body of the loop, the assignment x = x + 1 happens a * b times in the worst case.

Instead of describing this as O(N^2), I would describe it as O(ab), and then note for a ~= b ~= N that is O(N^2)

Upvotes: 0

Related Questions