Algorithms Question : Please explain me (with some examples) the best way to fin

Question

Algorithms Question: Please explain me (with some examples) the best way to find out big O (order of growth) from any number of given programming loops. Basically I need to have a better understanding of how i would figure out from any number of given loops whether the big O is nLogn or LogN or N cube...etc. I've basic understanding of simple "for..loop" that has Big O of N or N square, but i'm struggling to find out big O of Logarithm and also, in some cases even though there are couple of inner/outer loops, still big O can be N only. Please explain me with different examples so that i would be able to figure out Big O from any number of loops under any conditions.

Explanation / Answer

1) O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.

For example swap() function has O(1) time complexity.
A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1).

2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity.

3) O(nc): Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n2) time complexity

For example Selection sort and Insertion Sort have O(n2) time complexity.

4) O(Logn) Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

For example Binary Search has O(Logn) time complexity.

5) O(LogLogn) Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.

How to combine time complexities of consecutive loops?
When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

How to calculate time complexity when there are many if, else statements inside loops?
worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case. We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.
For example consider the linear search function where we consider the case when element is present at the end or not present at all.
When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.

here is a set of examples

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.