2

In the analysis of the time complexity of algorithms, why do you take only the highest growing term?

My thoughts are that time complexity is generally not used as an accurate measurement of the performance of an algorithm but rather used to identify which group an algorithm belongs to.

Consider if you had separate loops but each have nested loops of two levels, both iterating through n items such that the total complexity of the algorithm is 2n^2

Why is it taken that this algorithm is complexity of O(n^2)? rather than O(2n^2)

My other thoughts are, n^2 defines the shape of the computation vs input length graph or that we consider parallel computation when calculating the complexity such that O(2n^2) = O(n^2)

Its true that Ax^2 is just a scaling of x^2 the shape remains quadratic

My other question is consider the same two separate loops, now the first iterating through n items and the second v items such that the total complexity of the algorithm is n^2 + v^2 if using sequential computation. Will the complexity be O(n^2+v^2)?

Thank you

2 Answers 2

2

So first let me observe that two loops can be faster than one if the one does more than twice as much work in the loop body.

To fully answer your question, big-O describes a growth regime, but it doesn't describe what we're observing growth in. The usual assumption is something like processor cycles or machine instructions, you can also count floating-point operations only (common in scientific computing), memory reads (probe complexity), cache misses, you name it.

If you want to count machine operations, no one's stopping you. But if you don't use big-O notation, then you have to be specific about which machine, and which implementation. Don Knuth famously invented an assembly language for The Art of Computer Programming so that he could do exactly that.

That's a lot of work though, so algorithm researchers typically follow the example of Angluin--Valiant instead, who introduced the unit-cost RAM. Their hypothesis was something like this: for any pair of the computers of the day, you could write a program to simulate one on the other where each source instruction used a constant number of target instructions. Therefore, by using big-O to erase the leading constant, you could make a statement about a large class of machines.

It's still useful to distinguish between broad classes of algorithms. In an old but particularly memorable demonstration, Jon Bentley showed that a linear-time algorithm on a TRS-80 (low-end microcomputer) could beat out a cubic algorithm on a Cray 1 (the fastest supercomputer of its day).

To answer the other question: yes, O(n² + v²) is correct if we don't know whether n or v dominates.

0
1

You're using big-O notation to express time complexity which gives an asymptotic upper bound .
For a function f(n) we define O(g(n)) as the set of functions

O(g(n)) = { f(n): there exist positive constants c and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}


Now coming to question,
In the analysis of the time complexity of algorithms, why do you take only the highest growing term?
Consider an algorithm with, f(n) = an2 +bn +c
It's time complexity is given by O(n2) or f(n) = O(n2) because there will always be constants c' and n0 such that c'g(n) ≥ f(n) i.e. c'n2 ≥ an2 +bn +c , for n ≥ n0
We consider only higher growing term an2 and neglect bn+c as in the long term an2 will be much bigger than bn +c (eg.for n=1020, n2 is 1020 times larger than n)
Why is it taken that this algorithm is complexity of O(n^2)? rather than O(2n^2)
When a constant is multiplied it scales the function by constant amount, so even though 2n2 > n2 we write time complexity as O(n2) as there exists some constants c', n0 such that c'n2 ≥ 2n2
Will the complexity be O(n^2+v^2)
Yes, the time complexity will be O(n2 + v2) but if one variable dominates it will be O(n2) or O(v2) depending upon which dominates.

My thoughts are that time complexity is generally not used as an accurate 
measurement of the performance of an algorithm but rather used to identify 
which group an algorithm belongs to. 

Time complexity is used to estimate performance in terms of growth of a function. The exact performance of algorithm is hard to determine precisely due to which we rely on asymptotic bounds to get rough idea about performance for large inputs
You can take the case of Merge Sort (O(NlgN)) and Insertion Sort(O(N2)). Clearly merge sort is better than insertion sort in terms of performance as NlgN < N2 but when the input size is small (eg. N=10) Insertion sort outperforms merge sort mainly because the constant operations in Merge Sort increases it's execution time.


4
  • Can you please explain why Insertion sort outperforms Merge sort when N=10?
    – Malemna
    Mar 23, 2021 at 21:55
  • Because the constant operations in merge sort are much more than in insertion sort. N=10 was just an example of small input size. What I meant to say was that there will always be some N, such that C1*N < C2*lgN ( resulting in C1*N*N < C2*N*lgN). The value of such N will depend on various factors like efficiency of Interpreter, type of language used(machine vs high-level), CPU type etc. Consider some machine implements insertion sort and merge sort in 8n^2 and 64nlgn steps respectively. Here, insertion sort is better till n=43. Mar 24, 2021 at 1:52
  • Oh you mean the operations of constant time complexity, you really have to describe your thoughts a bit better. Otherwise, its going to be difficult for someone to hire you. But i understand it, thank you
    – Malemna
    Mar 24, 2021 at 14:47
  • Look at the way David Eisenstat has describe concepts, its very clear.
    – Malemna
    Mar 24, 2021 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.