1

Is it possible I am completely overthinking the complexity of an operation when I should only count it as one? This is an assignment question I have from my class.

Algorithm Power(n)
Pre: n :: Integer, n > 0
i = 1
while (i < n)
  print i
  i = i * 3
done

I am completely unsure of myself and think I am over-thinking the question

the time complexity O(N) before simplification would be O(n) = 1 + (3n + ? + 1) The amount of times i = i*3 is done is once per loop but the variable "i" grows at an accelerating rate per iteration does this actually matter or am I over-thinking things too much?

Is it O(n) because it is just one loop or more complex than that and something along the lines of O(log n) or O(n^(1/3)) due to "i" accelerating?

1
  • @JonathonReinhart My bad. Thought it wrongly. Commented Jan 24, 2014 at 20:17

1 Answer 1

0

You're correct that it is not O(n). A single level of loop corresponds to O(n) only when the loop counter (in this case i) increases linearly relative to n. As to whether it's O(log n) or O(n^(1/3)), I'll leave it to you to figure out since this is for an assignment.

1
  • Thank you, it should be easy for me to figure out as long as I know I am not over complicating things.
    – Lycius
    Commented Jan 24, 2014 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.