-
Notifications
You must be signed in to change notification settings - Fork 0
/
Analysis.txt
32 lines (27 loc) · 1.54 KB
/
Analysis.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Task 0:
Both times we are looking up a specific collection element by index - this is a static complexity operation.
Thus: O(1)
Task 1:
Iterating through for loop has complexity O(n).
Some number of computations must be performed for each row in the input files.
These computations (adding item to collection) have static complexity O(1).
Thus: O(n)
Task 2:
Even though in the first for loop there is an inner for loop present, it has static size - running exactly twice.
The other for loop only loops through unique phone numbers. Worst case this will be same size as the calls list size.
Thus same as for the above tasks apply:
O(n)
Task 3:
First for loop goes through each record in calls input list - for loop has complexity O(n).
Sorting the list has worst case complexity in this task: O(n log n) which way worse than O(n) - thus we can neglect the O(n).
Thus: O(n log n)
Task 4:
The for loops go through each record in the input data sets - for loops have complexity O(n).
List subtraction needs to iterate through one list, which is complexity O(n) ,
and then find if current element is present in the other list (and remove if true).
Such lookup would presumably be lower complexity than O(n), hopefully O(log n).
Sorting the list has worst case complexity in this task: O(n log n) which way worse than O(n) - thus we can neglect the O(n).
Thus: O(n log n)
All tasks:
Single line printouts have static compexity O(1) as these occur just once, thus considered negligible.
Printouts within the for loops in worst case would be same as input data size O(n).