I was recently viewing Andrew Ng's deep learning specialization lectures and I came forward to the following imageenter image description here

It is pretty obvious how the above function( x1 XOR x2 XOR x3..... XOR xn) can be implemented using multiple layers of a neural network. Ng told in the lecture that it is also possible to implement the above function using just a single hidden layer of NN. Is it possible ? If so , how? Also , what will be the time complexity difference between a single hidden layer of NN vs multiple layers of NN for the above function?

  • $\begingroup$ Not so obvious to me. Could you add some context? $\endgroup$ Oct 20, 2017 at 16:40
  • $\begingroup$ What do you mean by complexity difference? The tag time-complexity is about computational complexity (roughly, computational time as a function of sample size). $\endgroup$ Oct 20, 2017 at 16:47
  • $\begingroup$ @generic_user Here is the link of the video I am talking about :-coursera.org/learn/neural-networks-deep-learning/lecture/rz9xJ/… $\endgroup$ Oct 20, 2017 at 16:47
  • $\begingroup$ @RichardHardy Sorry I was talking about with reference to time complexity only. $\endgroup$ Oct 20, 2017 at 16:49
  • $\begingroup$ I was asking about time complexity because Andrew Ng told that the time complexity for a multi- layered neural network for the above function will be less as compared to that of a single layer of NN. $\endgroup$ Oct 20, 2017 at 16:56

2 Answers 2


He's "hand waving" here. The logic goes like this. You have N logical inputs, which means that the truth table has N dimensions with two values each, so its volume is $2^N$. Hence, he says, you need $2^n$ neurons in the hidden layer, followed by one output. Imagine multi-class classification network such as softmax.

That's how he's saying that you need a very wide $2^N$ node hidden layer, instead of a deep one with only $N\log_2 N$ nodes. What he's not talking about is the problem of separability, i.e. why would you need $2^N$ neurons in the hidden layer.

  • $\begingroup$ That was such a lucid explanation. Now I got the gist of it. Thanks! $\endgroup$ Oct 20, 2017 at 18:14

You can do a single hidden layer NN, or do a multi-layer NN. To do a single hidden layer, you need $2^N$ hidden units, each unit is matching with one of the possible enumerations of the $N$ inputs (each input can be $0$ or $1$, so total enumerations is $2^N$). For a multi-layer NN, you are building a binary tree so complexity is $O(\log N)$.

Note during the lecture Andrew Ng said for single layer you can technically only use $2^{N-1}$ hidden units. I believe this is a mistake but I hope someone can confirm.

  • $\begingroup$ If you can;t give a definitive answer you should give an answer. $\endgroup$ Feb 22, 2018 at 2:14
  • $\begingroup$ sorry I'm not sure if I understand your comment. $\endgroup$
    – George Han
    Feb 27, 2018 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.