I am taking an intermmediate course related to programming and analysis of system. I have a teacher that give us two tasks during the semester that are somewhat beyound the purpose of the course that is more toward the basics. The tasks that I am asked is "Dissert about the analysis of complexity of algorithm. In this dissertation,classify the four ordering algorithms (bubble sort,selection sort, merge sort e quick sort) in the different orders in the different order of asymptotic notation".

We have to go and do all research ourselves since this theme was not taught at school. To start off can you help how to tackle this problem. I read about asymptotic notation and it spinned my head.


Asymptotic notation utilizes the idea that we don't really know how much exact time an algorithm will run. For instance, we don't know what CPU the user is using, what other programs are running on his computer, etc.

The idea of asymptotic notation is to "capture" how the running time of an algorithm increases with respect to the input size. For example, linear running time $O(n)$ would mean that the running time of the algorithm on an array with 2 million values would be close to twice the running time of the algorithm on an array with 1 million values.

We can define the "running time" of an algorithm to be the number of "steps" it does. You can think of a "step" to be a CPU cycle. In formal computer science this is defined in a different way though.

Let $f$ be some function, that tells us how much "running time" the algorithm we use will require for a problem of size $n$.

Then, we can say that the algorithm we use is linear, if there is a constant $c$ such $f(n)\le c\cdot n$. This is denoted by $f=O(n)$.

Another example, would be when $f(n)\le c\cdot n^2$, and we say that $f=O(n^2)$. This means that the running time of something twice as large will be 4 times higher. and the running time of something 10 times larger will take 100 times more time.

This can be generalized to say that if $g$ is some function and $f(n)\le c\cdot g(n)$ then $f=O(g)$.

I hope I managed to help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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