Okay

so quiz is over.

Looks reasonable.

So

welcome to the last lecture of SMAI.

We're going to try start a complex

a new chapter

which is complexity theory.

Complexity is an important consideration in symbolic AI

and any other form of AI as well.

I think it's

since anything that's algorithm based

you need to understand complexity

and I'm assuming that you have studied that somewhere in your bachelors

and that you've

probably long forgotten

so I'm going to highlight certain portions of it.

So to kind of set the stage

let's consider we have an algorithm

or actually three algorithms.

One of them has

and we're going to look at what that means

linear complexity

the other

one quadratic, and the last one exponential.

If you basically apply this thing to problems of different sizes

right

I've given ourselves

a couple of sizes here

one

five

up to a million

then you can see that the runtime

basically from when you start the algorithm to when you have a result

varies quite differently

right?

For small sizes

what's happening here?

Something is wrong with the table

it should all be one step down here.

I wonder how that happened.

In the case of problems of size one

here

sorry

the formula

the actual runtime of

something of size n is 100 times n microseconds

we have here in the quadratic algorithm

we

have 7 n squared microseconds