Q:

analysis Big Oh notation pseudocode

I'm having trouble getting my head around algorithm analysis. I seem to be okay identifying linear or squared algorithms but  am totally lost with nlogn or logn algorithms, these seem to stem mainly from while loops? Here's an example I was looking at:
Algorithm Calculate(A,n) 
Input: Array A of size n 
t←0 
for i←0 to n-1 do 
   if A[i] is an odd number then 
      Q.enqueue(A[i]) 
   else 
      while Q is not empty do 
         t←t+Q.dequeue() 
while Q is not empty do 
  t←t+Q.dequeue() 
return t 

My best guess is the for loop is executed n times, its nested while loop q times making NQ and the final while loop also Q times resulting in O(NQ +Q) which is linear?

A:

First, lets assume that Q is initially empty.
Q will only grow at most at the same rate of the execution of the main loop.  For example, if we have iterated over 3 times so far, then Q is at most 3 elements large.  So when the inner while loop executes, it can at most only execute up to the current value of 'i'.  This means that the inner loop isn't a true case on n^2 (which isn't something you claimed anyway).  However, since Q can at most only be 'i' elements large, thus we know that O(calculate) <= O(2N).  And since in O notation we really don't care about scalars, then it is O(N).
Unless I'm wrong :)

