You are here:

C++/Complexity of Algorithms

Advertisement


Question
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:
http://www.csci.csusb.edu/turner/complexity
http://www.progressive-coding.com/tutorial.php?id=1
http://www.cs.bham.ac.uk/~mhe/foundations2/node121.html
http://en.wikipedia.org/wiki/Analysis_of_algorithms#Evaluating_run-time_complexi


---------- 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)?  

Answer
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.  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.