Questions tagged [complexity]
The complexity tag has no usage guidance.
3
questions
0
votes
1answer
37 views
Bubble Sort Time Complexity
I have a question regarding the worst case bubblesort time complexity.
What I have understood from David's lecture is the following:
Let's say we have an array of 4 elements, sorted in reverse order ...
1
vote
1answer
1k views
How is mergesort a O(n log n)?
After the lecture, I still do not quite understand why the upper bound of mergesort is n log n. I've tried to connect it with the phone book problem, which helped a little, but still don't really get ...
3
votes
4answers
5k views
I don't understand how the worst case performance of bubble sort is O(n^2)
The course materials say the worst case of bubble sort is O(n2) – when every item in the list is in the worst possible position. I'm having trouble wrapping my mind around this.
If I have a list of ...
