CODEWITHSUNDEEP
algorithm
Quang Ly
Quang Ly

Reputation: 31

Best running time

What is the best running time using theta notation for:

  1. Find an element in a sorted array
  2. Find an element in a sorted linked list
  3. Inserting an element in a sorted array, once the position is found
  4. Inserting an element in a sorted linked list, once the position is found

So far I have 2) is theta(n) and 4) is theta(1) only because I remembered my prof just said the answer in class, but is there an explanation on how to get these?

Upvotes: 2

Views: 58

Answers (1)

Ayon Nahiyan
Ayon Nahiyan

Reputation: 2200

First of all reading one of your answers it seems like you might be asking for complexity in O[big o].Theta notation is used when the complexity is bound asymptotically both above and below. Big O notation is for when the complexity is bound asymptotically, only above.

1. Find an element in a sorted array:

Using binary search it can be O(logn). But in Best case Ω(1)

2. Find an element in a sorted linked list

You can't use binary search here. You have to traverse the entire list to find a particular number. No way of going to a particular position without traversing numbers before(or after) it. So in worst case, you traverse n(length) times. So O(n)

Ω(1) because in best case you can find it in the beginning.

3. Inserting an element in a sorted array, once the position is found

O(n) since you have to shift all the numbers to the right of the position of new insertion place.

Ω(1) because in the best case you might just add it at the end.

4. Inserting an element in a sorted linked list, once the position is found

Ɵ(1) O(1) Ω(1), because adding a new element in a particular position (after you know the position and you have a pointer to that position) is theta(1)

Upvotes: 1

Related Questions