C++: Find Time Analysis Worst case O() of each member function with explanation:
1)
/** insert function:
parameters: obj
Description: inserts new elements into
the correct position in the
sorted array, sliding elements over the position to
right, as needed
**/
template <typename Object>
SortedArray::void insert(const Object &obj)
{
if (theSize >= theCapacity)
{
cout << "Error: there is no
enough memory space. " << endl;
return;
}
else
{
for (int i = ((2 * theSize) + 1);
(i >= 0 && SortedArray[i] > obj); i--)
SortedArray[i +
1] = SortedArray[i];
SortedArray[i + 1] = obj;
return (theSize + 1);
}
}
2)
/**
deleteMin function:
Description: remove the element in position 0, and
slide over allb other item
**/
templae <typename Object>
SortedArray::void deleteMin()
{
theSize--;
for (int i = 0; i < theSize; i++)
objects[i] = objects[i + 1];
}
3)
/**
Description: remove the last element in the sorted
array
*/
templae <typename Object>
void deleteMax()
{
theSize--;
}
//1
//In worst case function insert runs for :O(n) times
explanation:
if condition is satisfied , it runs for just O(1)times
but since we are considering worst case,
in else we have for loop which runs for 2*n times in worst case,
which means :2*O(n)= O(n)
//2
//worst case complexity is :O(n) where n is theSize
explanation:
since it has for loop, which runs for n times, where n is
theSize
it runs for O(n) times
//3
//worst case complexity is O(1)
explanation:
the function deleteMax has only one statement means runs in
O(1)
C++: Find Time Analysis Worst case O() of each member function with explanation: 1) /** insert function: parameters:...
write the interface of the following functions in the SortedArray.cpp, by the given functions in the SortedArray.h : #ifndef SortedArray_H #define SortedArray_H //INCLUDES #include <iostream> using namespace std; //---------------------------------- // SortedArray<Object> //---------------------------------- template <typename Object> class SortedArray { public: /** insert param: obj Description: insert new elements into the correct position in the sorted array, sliding elements over the position to right, as needed */ void insert(const Object &obj); /** Description: remove the element in position 0, and slide over...
vector.h: #ifndef VECTOR_H #define VECTOR_H #include <algorithm> #include <iostream> #include <cassert> template <typename T> class Vector { public: Vector( int initsize = 0 ) : theSize( initsize ), theCapacity( initsize + SPARE_CAPACITY ) { objects = new T[ theCapacity ]; } Vector( const Vector & rhs ) : theSize( rhs.theSize), theCapacity( rhs.theCapacity ), objects( 0 ) { objects = new T[ theCapacity ]; for( int k = 0; k < theSize; ++k) objects[ k ] = rhs.objects[ k...
1. void raw_push_front(const Object &x) { // insert x at the head of the list *without* using the iterator classes // Place your code here. } 2. void raw_push_back(const Object &x) { // insert x at the tail of the list *without* using the iterator classes // Place your code here. } #ifndef LIST_H #define LIST_H #include <algorithm> using namespace std; template<typename Object> class List { private: // The basic doubly linked list node. // Nested inside of List, can...
Language: C++ Complete this function 1.Object &raw_front() { // Return the element at the front of the list *without* using the iterator classes // (You may assume the list is not empty) // Place your code here. Code: #ifndef LIST_H #define LIST_H #include using namespace std; template class List { private: // The basic doubly linked list node. // Nested inside of List, can be public // because the Node is itself private struct Node { Object data; Node *prev;...
The function retrieveAt of the class arrayListType is written as a void function. Rewrite this function so that it is written as a value returning function, returning the required item. If the location of the item to be returned is out of range, use the assert function to terminate the program. note: please give all code in c++ below is the class and implementation(a test program would be helpful in determining how to use it): class arrayListType { public: ...
2.What is the order of complexity of the insert function in the worst case? You are required to provide a complexity function, and a proof that your complexity function belongs to a particular complexity class. In your complexity function you may specify the number of comparisons performed, as a function of input size. def insert(element, sorted): if len(sorted) == 0: return [element] else: if sorted[0] >= element: new_copy = sorted[:] new_copy.insert(0, element) return new_copy else: return [sorted[0]] + insert(element, sorted[1:])
#include <iostream> using namespace std; template <typename Item> class MyArray{ private: Item *myarray; int size; int used; void doubleSize(); public: MyArray(); ~MyArray(); int length(); void insertHead(Item i); void insertTail(Item i); void deleteHead(); void deleteTail(); void sortAscending(); void sortDescending(); Item operator [](int i){ return myarray[i]; } }; template <typename Item> MyArray<Item>::MyArray(){ size = 5; used = 0; myarray = new Item[size];...
(C++) (VISUAL STUDIO) Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we cannot insert the next element even if there is a space in front of queue. Efficiently implement a queue class using a circular...
This project is divided into 3 parts: Part 1. Create a new project and download the arrayList and unorderedArrayList templates that are attached. Create a header file for your unorderedSet template and add it to the project. An implementation file will not be needed since the the new class will be a template. Override the definitions of insertAt, insertEnd, and replaceAt in the unorderedSet template definition. Implement the template member functions so that all they do is verify that the...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a “data” value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr. Write the (single line) method declaration/specification. Write the method definition/implementation. Test by running the main() function below and capture the console...