Questions tagged [complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer

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 ...
user avatar
1 vote
1 answer

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 ...
user avatar
  • 105
3 votes
4 answers

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 ...
user avatar