algorithm - Time Complexity with increasing queue size -
i've searched google , stackoverflow past half hour or so, and, while i've found lot of interesting information, have yet find solution problem. think should simple answer; don't know how answer it.
i'm using following loop in program i'm working on (this pseudocode of algorithm, obviously):
while q not empty x = q.dequeue() for(i = 1 n) if x.s[i] = 0 y = combine(x, i) q.add(g[y]) in loop:
- q queue
- x object contains integer array s
- n integer representing problem size
- y new instance of same type of object x
- combine method returns new object of same type x
- combine contains loop, has worst-case time complexity of o(n)
my question how should trying calculate time complexity of loop. because i'm potentially adding n-1 items queue on each loop, i'm assuming increase complexity beyond simple o(n) normal loop.
if need more information me this, please let me know , i'll can when can.
Comments
Post a Comment