1

I am trying to understand the time complexity.Someone here mentioned that the time complexity is O(n) , please find the image below: Since it's N(N+1)/2 , shouldn't it be O(n^2) as N(N+1) are in multiplication? Please correct me if I have misunderstood something.

enter image description here

Community
  • 1
  • 1
John
  • 1,210
  • 5
  • 23
  • 51

3 Answers3

4

The code above computes n(n+1)/2, but that doesn't mean it takes time O(n2). For example, consider this code:

int x = n*n;

This code computes n2, but it runs in time O(1).

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
1

You misunderstood the answer: when the author says "the sum of natural numbers 1 through N is N*(N-1)/2", he provides a closed form expression for computing the sum if all 100 numbers were present. This value is computed in O(1).

Computing the sum of the 99 numbers from the list that is given to us takes O(N).

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
1

Complexity is a measure of the resources required by an algorithm. In this case if the size n of the list doubles then the time required will also double. In other words the required time resource is proportional to n. This is expressed as O(n). It's irrelevant how long each step take; the only important thing is the amount of overall time taken in relation to the input.

sprinter
  • 27,148
  • 6
  • 47
  • 78
  • So, if `N=200` then the complexity would be `O(n^2)` ? Similarly if `N=300` , would it be `O(n^3)` ? – John Feb 11 '15 at 04:09
  • @John perhaps I didn't explain it very well. The complexity is O(n) irrespective of n. It's really just saying that the time taken will be proportional to n. – sprinter Feb 11 '15 at 04:17
  • Can't we use Binary search to find it in O(LogN) time as mentioned here http://java67.blogspot.com/2014/12/how-to-find-missing-number-in-sorted.html considering number from 1 to 100 are sorted? – John Feb 11 '15 at 08:18