C++/Complexity of Algorithms
QUESTION: Hello again,
Could you tell me how to find Complexity of Algorithms of the functions add and extract?
also if you know of a good website on Complexity of Algorithms, I appreciate it if yo send me a link.
thank you in advance
ANSWER: function add has to execute a loop (the while loop for determining the position of the item in the list) and other instructions which are executed either once or not at all.
the time taken to execute the loop varies, depending on
a. the value of the item we want to add
b. the number of items in the list
if there are N elements in the list,
in the best case, the while loop will execute once (the item is to be added at the beginning).
in the worst case, the while loop will execute N times (the item is to be added right at the end).
in other cases, the loop will execute somewhere between 2 and N-1 times.
the average is close to N/2.
if the time taken to execute the while loop once is C1 (a constant), and the time taken to execute the remaining instructions is C2 (another constant independant of N),
the total average time is C1/2 * N + C2
the highest power of N is 1, we have a linear algorith or one that executes in O(N) time.
function extract only looks at the head of the list, the time taken by it is a constant (does not depend on N). it executes in constant or O(1) time.
here are a few links:
---------- FOLLOW-UP ----------
QUESTION: Thank you for your explanation and the websites that really helped me.
just to see if I understood the concept right,
if I were to find the complexity of the function which would use our FilePrio, since there is only 1 loop (therefor linear)in the algorithm, that means the complexity is O(N)?
if you mean, a function that sorts an array using FilePrio:
if the number of elements in the array is N:
we need to add every element int the array to a FilePrio.
time taken to add one element to FilePrio is O(M) is the number of elements in FilePrio is M.
adding the first element would take O(1) time (FilePrio is empty)
adding the second element would take O(2) time.
adding the element i would take O(i) time. (FilePrio has i-i elements)
... adding the last element would take O(N) time. (FilePrio has N-1 elements)
total time taken for this part is:
O(1) + O(2) + ...... + O(N)
or O( N * (N-1) / 2 ) or O( N^2 ) ie. quadratic.
to extract an element takes constant time, we need to now extract N elements, time taken for this step is N * O(1) ie. O(N)
time complexity of the algorithm (both the steps) is therefore O( N^2 ) + O(N)
ignoring the less significant term, we get O( N^2 ) or quadratic.