Big Oh notation pseudocode analysis
I am having trouble parsing algorithms. I seem to be good at linear or quadratic algorithms, but completely lost with the nlogn or logn algorithms, do they seem to be mainly related to loops? Here's an example I looked 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 that the for loop is executed n times, its nested while q loop does NQ and the final while loop also Q times results in O (NQ + Q), which is linear?
source to share
First, suppose Q is initially empty.
Q will only grow at the same rate of execution of the main loop. For example, if we have repeated three times so far, then Q has at most 3 elements. Therefore, when the inner while loop is executing, it can, at most, only execute the current value of "i". This means that the inner loop is not a true case on n ^ 2 (which is not what you claimed anyway). However, since Q can be nothing more than just i elements, we know that O (computes) & lt = O (2N). And since in O-notation we don't really care about scalars, it is O (N).
If I am wrong:)
source to share