CODEWITHSUNDEEP
algorithmdata-structurestime-complexitybig-o
RVER12321312
RVER12321312

Reputation: 81

Time complexity will two O(n^2) algorithms take the same amount of time?

I am having trouble fully understanding this question:

Two O(n2) algorithms will always take the same amount of time for a given vale of n. True or false? Explain.

I think the answer is false, because from my understanding, I think that the asymptotic time complexity only measures the two algorithms running at O(n2) time, however one algorithm might take longer as perhaps it might have additional O(n) components to the algorithm. Like O(n2) vs (O(n2) + O(n)).

I am not sure if my logic is correct. Any help would be appreciated.

Upvotes: 3

Views: 2426

Answers (2)

Kaidul
Kaidul

Reputation: 15885

Yes, you are right. Big Oh notation depicts the upper bound of time complexity. There might some extra constant term c or smaller term of n like O(n) added to it which won't be considered for time complexity.

Moreover,

for i = 0 to n
    for j = 0 to n
        // some constant time operation
    end
end

And

for i = 0 to n
    for j = i to n
        // some constant time operation
    end
end

Both of these are O(n^2) asymptotically but won't take same time.

The concept of big Oh analysis is not to calculate the precise amount of time a program takes to execute, it's not about counting how many times a loop iterates. Rather it indicates the algorithm's growth rate with n.

Upvotes: 4

Henry
Henry

Reputation: 43738

The answer is correct but the explanation is lacking.

For one, the big O notation allows arbitrary constant factors. so both n2 and 100*n2 are in O(n2) but clearly the second is always larger.

Another reason is that the notation only gives an upper bound so even a runtime of n is in O(n2) so one of the algorithms may in fact be linear.

Upvotes: 3

Related Questions