Describe the process of analyzing the Big O Notation for a Stack or Queue Stack

Question

Describe the process of analyzing the Big O Notation for a Stack or Queue

Stack is a data structure which follows Last In First Out method.

If we want to search, we need to search all the elements in stack which takes n in worst case

Following 3 operations are performed on the top of the stack and hence takes O(1) complexity

push - pushes element into stack

pop - removes first element

peek - shows the top element

QUEUE

WORST CASE

AVERAGE CASE

BEST CASE

MEMORY ALLOCATION ANALYSIS

STACK

QUEUE

RAM MEMORY

STACK MEMORY

HEAP MEMORY

VIRTUAL MEMORY

QUEUE

WORST CASE

AVERAGE CASE

BEST CASE

CPU Memory Management Disk Virtual Cache Ram Storage 2000 How Stuff Works, Inc

Explanation / Answer

Let us first understand the "O" in O(n) complexity. The O here represents the worst case time it will take in performing a process. It is usually the most important complexity parameter as we are least interested in the best case time of a process and average case time. All we want to know from any algorithm is that even in the worst case of inputs, how well will my algorithm perform.

O(n) means that for 'n' number of inputs, it will take a time of n*c, where 'c' is some constant amount of time.

So for 10 inputs, time will be directly propotional to 10, for 20 directly propotional to 20, and so on.

Now let us consider the worst case of searching for something in the stack. In stack there is no option available of random access to any stack entry. Hence we have to go one by one from top of the stack to the bottom to search for things. So in the worst case the element to be searched would either be the last entry in the stack or it would not be present in stack for which it would take a time of n*c to search elements, where 'n' is number of stack entries and 'c' is the time it takes to search a single entry in stack.

Hence the complexity comes to be O(n).

As the push, pop and seek is done only on the first(top) element of the stack hence in the worst case even it will take time equal to 1*c, where 'c' is the amount of time it takes to acces one entry in stack. Hence it is in O(1).

Now coming to second part of the question:memory.

RAM memory is computer's memory. It is used during processes of execution of computer's program and any and every computer process is being occupied in RAM.

Every program in exceution has its own stack memory that it uses for calling its sub parts or functions or operations in execution.

Heap memory is shared by all active programs and contains the definition and implementation of all the functions in the program.

Virtual memory is the one that seems to exist by a process but actually doesn't. A detailed discussion on it goes a very long and complicated way.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.