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: 318
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