0.0 Big O

Question 1

What is the model size for 0-R

Answer 1

Most frequent class O(1)

Question 2

What is the model size for a general probabilistc learner

Answer 2

For m attributes with k possible values and C classes, this mean O(Ck^m) instances

Question 3

What is the training complexity for a k-NN

Answer 3

O(1) (some people even say it is non-existent, but space complexity of training is O(Nd) since you need to store the data which also takes time).

N = number of training examples,

d = dimensionality

c = number of classes.

Question 4

What is the training complexity for a Nonlinear non-approximate SVM

Answer 4

Nonlinear non-approximate SVM is O(N²) or O(N³) depending on the kernel.

You can get a O(N³) down to O(N^2.3) with some tricks.

N = number of training examples,

d = dimensionality

c = number of classes.

Question 5

What is the training complexity for a Naive Bayes

Answer 5

Naive Bayes is O(Nd), all it needs to do is computing the frequency of every feature value d_i for each class.

N = number of training examples,

d = dimensionality

c = number of classes.

Question 6

What is the testing complexity for k-nn

Answer 6

k-NN is in O(Nd) since you have to compare the test point to every data point in your database.

N = number of training examples,

d = dimensionality

c = number of classes.

Question 7

What is the testing complexity for Naive Bayes

Answer 7

O(cd) since you have to retrieve d feature values for each of the c classes.

N = number of training examples,

d = dimensionality

c = number of classes.

Question 8

What is the training complexity for a Approximate SVM

Answer 8

O(NR) where R is number of iterations.

N = number of training examples,

d = dimensionality

c = number of classes.