Complexities

Question 1

Counter

Answer 1

N complexity , especially if variable is the counter ( how many you want, x , 1 to x , Proportinsl to counter thus n complexity )

Question 2

First fit / first fit decreasing
How to get there

Answer 2

N sqaured

• count the comparisons needed each pass
• using worse case scenario (which is Esch weight saturated as Box Esch time)
• comparisons go 1,2 ,3 ,4

Hence triangle number = n2

Question 3

Why is triangle numbers n2 complexity

Answer 3

1,2,3 is the sum of N
We know this is 1/2n (n+1)
However might be n-1 , hsve tk chekc the order of triangle numbers and compare

Alternatively find nth term, increase by 1 each time divide by 2 and sqaure, Compare etc..

Question 4

Quick sort
Worse case

Answer 4

N2 , 1/n (n-1)
Worse case already / reverse ordered

Count final number of comparisons total and see this is one behind the 1/n (n+1) formula , therefore n-1

Question 5

Bubble sort
Why

Answer 5

Again n2 , 1/n (n-1)

Worse case is if comoleltey unordered
Ad compariojs are always 1 less than sublist, 5,4,3,2,1 = triangle , and adjust

Question 6

DIJKSRRA prims and Kruskal complexity

Function of?

Answer 6

N 2

Kruskal prims as a function of the number of edges

And DIJKSRRA as a function of nodded