1

I am studying algorithms, but the calculations to find Time Complexity are not that much easy for me, it is hard to remember when to use log n, n log n, n^2, n^3, 2n, etc, my doubt is all about how to consider these input functions while computing the complexity, is their any specific way to calculate the complexity ,like using for loop take's this much complexity always and so on....?

Keyur Shah
  • 45
  • 2
  • 6
  • 4
    possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – jojo May 14 '15 at 06:12

2 Answers2

0

There are many links on how to roughly calculate Big O and its sibling's complexity, but there is no true formula.

However, there are guidelines to help you calculate complexity such as these presented below. I suggest reviewing as many different programs and data structures to help familiarize yourself with the pattern and just study, study, study until you get it! There is a pattern and you will see it the more you study it.

Source: http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/

  1. Nested loops are multiplied together.
  2. Sequential loops are added.
  3. Only the largest term is kept, all others are dropped.
  4. Constants are dropped.
  5. Conditional checks are constant (i.e. 1).
jojo
  • 1,135
  • 1
  • 15
  • 35
0

Log(n): when you are using recursion and a tree is generated use log(n). I mean in divide and conquer when you are diving problem into 2-halfs actually you are generating a recursive tree.

its complexity is Log(n), why ? because its a binary tree in nature and for binary tree we use Log(Base2)(n).

try yourself: suppose n=4(Elements) so log(base2)(4)=2, you divide it into equal half.

nLog(n): remember Log(n) its was division till single element. after that you start merging sorted elements that take liner time

in other words Merging of elements has complexity "n" so total complexity will be n(Merging) + Log(n)(Dividing) which is finally become nLog(n).

n^2: when you see a problem is solved in two nested loop then Complexity is n^2. i.e Matrix/2-D arrays they computed in 2 Loops. one loop inside the outer Loop.

n^3: oh 3-D arrays, this is for 3 nested loops. loop inside loop inside loop.

2n: thanks you did not forgot to write "2" with this "n" otherwise I forgot to explain this.

so "2" in here with "n" is constant just ignore it. why ?. because if you travel to other city by AIR. you will count only hours taken by flight not the hours consumed in reaching AIR port. I mean this is minor we remove constant.

and for "n" just remember this word "Linear" i.e Big-O(n) is linear complexity. Sadly I discovered there is no Algorithm that sort elements in Linear time. i.e just in one loop.(Single array traversal).

Things To Remember:

Nominal Time: Linear Time, Complexity Big-O(n)

Polynomial Time: Not Linear Time, Complexity Big-O[ log(n), nlog(n), n^2, n^3, n^4, n^5).

Exponential Time: 2^n, n^n i.e this problem will solve in exponential time i.e N^power(n) (These are bad bad bad, not called algorithm)

Kaleem Ullah
  • 6,799
  • 3
  • 42
  • 47