Suppose there is a unsorted array A, and it contains an element x (x is the pointer of the element), and every element has a satellite variable k. So, we can get the following time complexity (for worst cases):

If we want to **Search** for a particular K, then it costs O(n).

if we want to **Insert** an element, then it costs O(1), because A just adds the element to the end.

What if we know x, then **Delete** it from the array A?

We have to *Search* for x.k first and get the index of x, then *Delete* x via its index in A, right?

So for **Delete**, it costs O(n) too, right?

thanks

Yes. It takes `O(n)`

time to find the element you want to delete. Then in order to delete it, you must shift all elements to the right of it one space to the left. This is also `O(n)`

so the total complexity is linear.

Also, if you're talking about statically allocated arrays, insert takes `O(n)`

as well. You have to resize the array in order to accommodate the extra element. There are ways to amortize this running time to `O(1)`

though.

Yes, that's right. Also, if it's an array, deleting alone will take `O(n)`

time because after you delete the element, you'll need to shift all the elements to the right of that element one place to the left. So, even if you know x (for example, you will only delete the first element), it will take `O(n)`

time.

Finding the element with a given value is linear.

Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element.

Similar Questions

Can someone please explain to me how to calculate the complexity of the following recursive code: long bigmod(long b ,long p, long m) { if(p == 0) return 1; else if(p % 2 == 0) return square(bigmod(b,

I read this article Retiring a Great Interview Problem, the author came up with a work break problem and gave three solutions. The efficient one uses memoization algorithm and the author said its wors

What is the time complexity of this loop since it does not iterate by 1: while (parser.hasNext()) { token = parser.next(); if (isOperator(token)) { op2 = (String)(stack.pop()); op1 = (String)(stack.po

i am trying to do a study on Space complexity of bubble sort algorithm what i know that the Space complexity of bubble sort algorithm is O(1) given the below bubble sort algorithm how can i change the

I am reading some information on time complexity and I'm quite confused as to how the following time complexities are achieved and if there is a particular set of rules or methods for working this out

So given the following program: Is the time complexity of this program O(0)? In other words, is 0 O(0)? I thought answering this in a separate question would shed some light on this question. EDIT: Lo

Advice? Given an unsorted array and the number of elements, for each element i have to print the number of elements between itself and the farest element in the array that is smaller than him, if the

Is it possible to calculate the time complexity of genetic algorithm? These are my parameter settings: Population size (P) = 100 # of Generations (G) = 1000 Crossover probability (Pc) = 0.5 (fixed) Mu

What is the time complexity of simple SQL statements like the following? INSERT into table (col1, col2, col3) values (a, b, c) How does it depend on the following: size of the table datatype o

From Introduction to Algorithms 2nd edition I got this deletion algorithm: /* RB-DELETE(T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ nil

From an online notes, I read the following java code snippet for reversing a string, which is claimed to have quadratic time complexity. It seems to me that the “for” loop for i just iterates the whol

I found a code which will detect common elements in an unsorted array. The program runs in linear time! But i did not understand the logic of the program. It would be very helpful if some one could ex

I want to know what's the worst case time complexity of put/get methods of HashMap incase the object used as a key always returns hashcode as 1. In my understanding: As every key has the same hashcode

I have an assignment that wants me to write an ternary search algorithm and compute its time complexity afterwards. I was able to write an algorithm for it but I couldn't come up with any ideas how to

Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?

In an unsorted array, we have to replace every element by the first element to the right that is larger than the current element. If none of the elements to the right are bigger then it should be repl

I'd like to determine time complexity of a printf such as: { printf(%d, i); } Or: { printf(%c, array[i]); } Is it correct to assume that time complexity of a printf is always O(1) or not? [EDIT]

Could you please explain me the thing: how does LZ complexity algorithm incorporate with data compression? Does it (or meant to) compress data or it only estimates the number of unique substrings in v

It's diffcult for me to understand logarithmic complexity of algorithm. For example for(int j=1; j<=n; j*=2){ ... } Its complexity is O(log2N) So what if it is j*=3? The complexity will then be O

This question already has an answer here: Linear time algorithm for 2-SUM 3 answers This is a generalization of the 2Sum problem Given an unsorted array of numbers, how do you find the pair of

I was learning about algorithms and time complexity, and this quesiton just sprung into my mind. Why do we only analyze an algorithm's time complexity? My question is, shouldn't there be another metri

for a M X M array what is the time complexity of finding an element assuming the array is sorted in all the direction?

I was reading this question. The selected answer contains the following two algorithms. I couldn't understand why the first one's time complexity is O(ln(n)). At the worst case, if the array don't con

I'm pretty new to databases, so forgive me if this is a silly question. In modern databases, if I use an index to access a row, I believe this will be O(1) complexity. But if I do a query to select an

So I'm curious to know what the running time for the algorithm is on on priority queue implemented by a sorted list/array. I know for an unsorted list/array it is O((n^2+m)) where n is the number of v

In the worst case while appending an element(inserting at end) array can be full. So a new array is created and n elements are copied from this array to the new array. I read in literature that worst

I have followed median compare algorithm to find median of two sorted arrays and implemented in java. As per algorithm time complexity is O(lgn) but since it involves creating subarrays(method createS

Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Personally I think, the time compl

I am working on an assignment and don't get answer for some of questions. I Have been asked : Input: an array A of length N that can only contain integers from 1 to N Output: TRUE - A contains duplica

I was reading Skiena's Algorithm Design Manual, and couldn't solve this problem. Suppose an array A consists of n elements, each of which is red, white, or blue. We seek to sort the elements so that a

I have an integer array, and some x integer value. I need to loop over the array comparing if the current array value is equal to x. If so, the loop breaks. The worst-case time complexity is W(n) = n

foo = [] i = 1 while i < n: foo= foo + [a] i*=2 What is the time complexity of this code? My thoguht is: the while loop does log(n) iteration. For each iteration new list is created. So, the tot

I try calculate time complexity for the following algorithm. private void encrypt() { M = new BigInteger(64,random); C = M.multiply(k).mod(N); // O(n^2) } private void decrypt() { kk= k.modinverse(N);

Can you explain me how to find time complexity for this sum1=0; for(k=1;k<=n;k*=2) for(j=1;j<n;j++) sum++ I am taking consideration of N as base, and tried calculating how many iteration happen

What's the big-O time complexity of the two methods listed below? Is method 1 O(log n²) or O(log n)? Is method 2 O(n²) or something else? public static void method1(int n) { int k = 0; for (int i = 1;

Is there an algorithmic approach to find the minimum of an unsorted array in logarithmic time ( O(logn) )? Or is it only possible in linear time? I don't want to go parallel. Thanks Michael

So one of the topics in my comp sci class is concerning time complexity and using arrays and linked lists as a good way to compare certain operations and what container is better at doing so, so you c

Mongodb supports many useful array operations such as $push and $pop but I can't seem to find any information about their algorithmic complexity nor how they are implemented to figure out their runtim

I have 2 arrays a of length n b of length m Now i want to find all elements that are common to both the arrays Algorithm: Build hash map consisting of all elements of A Now for each element x in B ch

I'm taking Data Structures and Algorithm course and I'm stuck at this recursive equation: T(n) = logn*T(logn) + n obviously this can't be handled with the use of the Master Theorem, so I was wonderin

The reason for posting this question comes from here Is there any Time complexity difference between the following Snippets of Code? Code Snippet A: public static void main(String[] args) { for (int

can we perform graph lookup( A and B is connected or not?) and connect( connect A and B) in log time using a single array? I learned some algo like: quick find (linear time in connect and constant tim

I would like to know the time complexity of the following algorithm. At first glance the time complexity looks to be O(n^5) and that is what is mentioned in majority of the sites i have seen on the in

i am given an array of integers which are not necessarily sorted. I have to find a pair of nos whose difference between each other is least compared to any of the other pair of nos in the array. the t

Can someone show me an example of deletion algorithm for a coalesced chained hash table? My insertion algorithm is like this: Insert (key) int p = hash(key) if d[p] = NIL then d[p] = key next[p] = NIL

This question already has an answer here: Finding contiguous ranges in arrays 5 answers You are given an Array of numbers and they are unsorted/random order. You are supposed to find the longes

So I have a random question when coding the image processing function that involves time complexity. The following is my original snippet of code: long start = System.currentTimeMillis(); for (int i

Could you please help me in understanding the Time Complexity for Divide and Conquer algorithm. Let's take example of this one. http://www.geeksforgeeks.org/archives/4583 Method 2: It gave T(n) = 3/2n

The time complexity of Redis' HDEL is O(N) (where N is the number of fields to be removed). I have a use case where the field must undergo a type conversion for every operation. How would I express th

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The executio