analysis Big Oh notation psuedocode

Posted by tesshu on Stack Overflow See other posts from Stack Overflow or by tesshu
Published on 2010-04-09T15:26:10Z Indexed on 2010/04/09 15:33 UTC
Read the original article Hit count: 289

Filed under:
|

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? Heres 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? I am probably totally wrong. Any help would be much appreciated. thanks

© Stack Overflow or respective owner

Related posts about big-o

Related posts about analysis