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

Popular posts from this blog

node.js - Using Node without global install -

How to access a php class file from PHPFox framework into javascript code written in simple HTML file? -

java - Null response to php query in android, even though php works properly -