Punit Jain

Ranch Hand

Posts: 1028

2

posted 5 years ago

hii, i m sorry if i am asking this in the wrong forum, i didn't found any specific forum for data structure.

can anyone tell me how we analyze an algorithm. also how we calculate the time and space complexity of any algorithm.

(ie. O(logn) for binary search)..

any examples...

Thank you...

can anyone tell me how we analyze an algorithm. also how we calculate the time and space complexity of any algorithm.

(ie. O(logn) for binary search)..

any examples...

Thank you...

Punit Jain

Ranch Hand

Posts: 1028

2

Tim Moores

Saloon Keeper

Posts: 3512

77

posted 5 years ago

If I understand you correctly, what you are trying to do is generate a complexity function for an algorithm that you have. If so, the usual way of doing that is to examine the amount of work done to handle the case where the number of objects in the collection to be processed is 1, then 2, then 3, and so on. In other words, you do this by hand, manually calculating each number.

At time, you need only n=1, n=2 and n=n' + 1 (in other words, figure out the value for any given number using one less than that number), but other times you might need more results. Based on the result, you should be able to come up with a mathematical formula that related the number of objects processed to its complexity. I recall that one of my high level math courses in college covered this. And there were several way to determine the formula based on the progression. But it has been a long time and I don't recall the details.

At time, you need only n=1, n=2 and n=n' + 1 (in other words, figure out the value for any given number using one less than that number), but other times you might need more results. Based on the result, you should be able to come up with a mathematical formula that related the number of objects processed to its complexity. I recall that one of my high level math courses in college covered this. And there were several way to determine the formula based on the progression. But it has been a long time and I don't recall the details.