-1

I have difficulty determining the execution time of each step in an algorithm. I just can't understand the logic.

We all know prior to determining the Big O or Theta in an algorithm, we have to calculate the execution time of each step, then we calculate the order based on the execution time.

I find it easier to calculate the order than the Big O or the Theta, but my issue is with calculating the execution time.

Example: 

for i=0  to **n** 

dothisStep

The execution time of this is : (n+1) which makes it an order of O(N)--this is an easy one and I understood why--my problem is with the "harder ones". Sometimes I'm supposed to get n(n+1)/2, sometimes n(n+1), but I just can't understand how or why! What are the rules?

Erick G. Hagstrom
  • 4,873
  • 1
  • 24
  • 38
napi15
  • 2,354
  • 2
  • 31
  • 55
  • 3
    This question/answers may help you : http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it/4852666#4852666 – Pierre Feb 02 '16 at 16:06
  • 1
    These mean the same thing: "Big O of N" == "order of N" == "O(N)". When we say "on the order of X" in this context, what is meant is "X is the dominating factor that determines runtime complexity. For large input we can ignore the other factors." You can see this means O(X). – Esoteric Screen Name Feb 02 '16 at 16:36

1 Answers1

1

I think something that will help you here when doing these problems is to think of what happens as n approaches infinity. In the example of n + 1, that + 1 becomes very insignificant in relation to n.

Your other example: n(n+1) - Again, adding 1 when n approaches infinity is very insignificant so we drop the + 1. This leaves n(n) which is n^2.

Andrew_CS
  • 2,542
  • 1
  • 18
  • 38