Questions tagged [complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...