CODEWITHSUNDEEP
arrayslinked-listtime-complexitybig-o
Naomi
Naomi

Reputation: 79

What are the running times of these?

I need to compare the worst case running time of a linked list vs an array.

If ordering must be preserved and the list/array already has n items, what will be the worst case running times for the following? And why?

These are the questions and my answers:

Adding an item to the front of a linked list. ANSWER ATTEMPT: O(1)
Adding an item to the front of a standard array. ANSWER ATTEMPT: O(n)

Accessing the (n/2):th item of a linked list. ANSWER ATTEMPT: O(n)
Accessing the (n/2):th item of a standard array. ANSWER ATTEMPT: O(1)

Deleting the (n/2):th item from a linked list. ANSWER ATTEMPT: O(1) - CORRECT ANSWER O(n)
Deleting the (n/2):th item from a standard array. ANSWER ATTEMPT: O(n)

Upvotes: 0

Views: 33

Answers (1)

letmutx
letmutx

Reputation: 1416

Adding an item to the front of a linked list. ANSWER ATTEMPT: O(1)

To add an element at the beginning of a list, you need to change some pointers only. So, its complexity is O(1).

Adding an item to the front of a standard array. ANSWER ATTEMPT: O(n)

In an array, to add an element at the beginning(or in the middle), all the elements stored after that index need to be shifted by one position. So, it takes O(n) in the worst case.

Accessing the (n/2):th item of a linked list. ANSWER ATTEMPT: O(n)

To access an element in a linked list, you need to traverse it from the beginning using next pointers as they are not contiguous in memory. So, it takes O(n) time.

Accessing the (n/2):th item of a standard array. ANSWER ATTEMPT: O(1)

Arrays are contiguous in memory. So, you can access the ith element using index in O(1) time.

All the answers except this one are correct.

Deleting the (n/2):th item from a linked list. ANSWER ATTEMPT: O(1)

Deleting the (n/2) th element is O(n) because access time of (n/2) th element is not O(1). You need to traverse until half of the array which is a O(n) operation.

Deleting the (n/2):th item from a standard array. ANSWER ATTEMPT: O(n)

Just as in the case of adding, you need to copy over the elements after the deleted index one step forward. So, it takes O(n) time.

Upvotes: 2

Related Questions