What is a novelty in a computer science PhD'
In computer science, perception of novelty varies greatly by subfield. In theory, they would consider a new algorithm a novel contribution. In other subfields like bioinformatics or compilers, a new application of an algorithm to a problem would be considered a novel contribution. In Human-computer interaction, improving our knowledge on how people interact with certain types of user interfaces would be a novel contribution. People doing research in architecture, graphics, networking, systems, etc. each have their own notion of what novelty means.

Your adviser is the best person to ask what constitutes a novel contribution in your subfield.

Standards for how much novel work you need to earn the PhD degree vary by University and by adviser. I've seen 100 page dissertations and 500 page dissertations. I've seen dissertations that don't seem to add much more than a single journal paper would, and I've seen dissertations that completely crack open a whole new field of research. 

Of course, you will have to meet whatever standards are set by your University and thesis committee. If you think their requirements are unreasonable or unfair, feel free to ask another question.