Algo: How to analyse the algorithm for its complexity ?

Question

Looking for basic steps to analyse the algorithm.

Answer 1

There is no generalized answer only few tips can be suggested -

1. An algorithm that does not contain any loops (for example: Write Text to Console, Get Input From User, Write Result To Console, a hash function etc) is O(1), no matter how many steps. The "time" it takes to execute the algorithm is constant (this is what O(1) means), as it does not depend on any data.

2. An algorithm that iterates through a list of items one by one has complexity O(n) (n being the number of items in the list). If it iterates two times through the list in consecutive loops, it is still O(n), as the time to execute the algorithm still depends on the number of items only.

3. An algorithm with two nested loops, where the inner loop somehow depends on the outer loop, is in the O(n^x) class (depending on the number of nested loops).

4. An binary search algorithm on a sorted field is in the O(log(n)) class, as the number of items is reduced by half in every step.

5. A recursive or iterative approach where we are using divide and conquer to solve some problem i.e. quicksort etc have O(nlog(n)).