analysis Big Oh notation psuedocode
- by tesshu
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
