algorithm - pseudopolynomial time and polynomial time -

i confused pseudopolynomial time in compare polynomial time

input(n); (int i=0; i<n;i++){      dostuff; } 

the runtime o(n) writing out number n takes x=o(log n) bits.

so, if let x number of bits required write out input n, runtime of algorithm o(2^x), not polynomial in x. conclusion correct?

edit: @ simple primetest.

  function isprime(n):   2 n - 1:      if (n mod i) = 0, return false   return true 

the runtime o(n). remember, formal definition of time complexity talks complexity of algorithm function of number of bits of input.

therefore, if let x number of bits required write out input n, runtime of algorithm o(2^x), not polynomial in x.

edit2: got points @ knapsack problem. // input:

 // values (stored in array v)  // weights (stored in array w)  // number of distinct items (n)   // knapsack capacity (w)    j 0 w do:  m[0, j] := 0    1 n do:  j 0 w do:      if w[i] > j then:          m[i, j] := m[i-1, j]      else m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 

if guys right mean knapsack problem has runtime o(n*w), therefore has polynomial time !

alex 64 push-ups everyday.

and

alex 2^6 push-ups everyday.

if above 2 lines mean same you, o(n) , o(2^x) doesn't matter :)

o(2^x)  => o(2^log_2(n))  => n [as know x^log_x(y) = y] 

the formal definition of time complexity talks complexity of algorithm function of number of bits of input.

yes, you're right. idea of big-o analysis growth rate of algorithm growth of input, not precise counting of how many times loop iterates.

as example, when n = 32, algorithm complexity o(2^5), growth of n, example when n = 1048576, complexity o(2^20). so, complexity increases input increases.

n or 2^(log_2(n)) presenting same numeric amount differently. long growth rate of algorithm linearly proportional growth rate of input, algorithm linear - no matter whether represent input n e^x or log(y).

edit

quoted wikipedia

the o(nw) complexity not contradict fact knapsack problem np-complete, since w, unlike n, not polynomial in length of input problem. length of w input problem proportional number of bits in w, log w, not w itself.

you first 2 snippet n has polynomial growth.