CODEWITHSUNDEEP
javatime-complexity
John
John

Reputation: 1220

Time complexity O(n) for finding missing number?

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

Upvotes: 1

Views: 585

Answers (3)

sprinter
sprinter

Reputation: 27966

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.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726609

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).

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372814

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!

Upvotes: 4

Related Questions