Big Oh

Use big Oh to show the running time of each function in a deque that uses a doubly linked list for its implementation, and the deque space storage.

Are each of these statements right? Either O(n) or O(1)

O(1) is the running time for the size() operation

O(1) is the running time for the empty() operation

O(n) is the running time for the front() and back() operations

O(1) is the running time for the insertFront(const Elem& e) and insertBack(const Elem& e) operations

O(n) is the running time for the removeFront() and removeBack() operations

Space usage of the deque is O(1)
closed account (49iURXSz)
Take a look at the standard library reference for deque:

http://www.cplusplus.com/reference/deque/deque/

Look for the complexity field.

** EDIT **
I can't verify if those statements are right without looking at how your deque is implemented. You have different member functions than those for the std::deque data structure.
Last edited on
From what you have posted at least some of those are wrong.

If you have to look through the list of things to find something, then it is O(n).
If you don't, then it is O(1).

For example, if your list looks like this:

1
2
3
4
5
6
7
8
9
class MyDeque
{
private:
  Node * _first;
  size_t _size;

public:
  ...
};

Then you wouldn't have to look through the items to find the first element, so it would be O(1).
But you would have to look through the items to find the last, so it would be O(n).

Hope this helps.
Ok thanks, I think I sort of understand. I'll look over it again.
Last edited on
closed account (48T7M4Gy)
The question is somewhat ambiguous depending on whether the either statement is part of the question or not.
Either O(n) or O(1)


http://en.cppreference.com/w/cpp/container/deque gives some definitive answers.
Topic archived. No new replies allowed.