-2

I am trying to understand what polynomial and exponential time is in relation to the big O notation.

I understand the basics of O notation such as linear is O(n) and O(n^2) is quadratic etc.

The only theory I have which I am not completely sure about is that

I have read this but it doesn't seem to be of much use.

I found on Wikipedia that polynomial is O(n^c) Am i right that the n is the varying number of input and c is the constant.

same with exponential? O(c^n)

If anyone could give a simple definition so I could understand it I would be greatly appreciated, thanks.

Community
  • 1
  • 1
Luke
  • 267
  • 2
  • 6
  • 16

1 Answers1

2

Polynomial bound:

Algorithm is upper bound by a polynomial on the input size n. --> poly(n)

Exponential bound:

Algorithm is upper bound by constant^poly(n) , where poly is some polynomial on input size n.

sanjeev mk
  • 4,178
  • 4
  • 39
  • 63