New answers tagged

1

The OP has already understood the solution, but still: findMinMax procedure given above is just finding the maximum and minimum element in the array. It has a runtime of O(N). swap procedure just swaps two array elements given by their indices, which is O(1). doSomething is an interesting procedure. It seems to be some kind of a variant of selection sort, ...


1

Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$. You could do this by initializing a (1-indexed) boolean array $used[\cdot]$ of length $n$, and setting $used[x]$ equals true whenever you set some $A[i]=x$. Now the question is how many times may $rand()$ be called in the worst ...


1

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized". The amortized cost per items is O(1), since the cost of adding n items individually is O(n). There are various ...


-1

Perhaps this is a reference to Cobham's thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis?wprov=sfla1. Usually the word used is "feasible" though.


1

https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation. Array: Access - O(1) // we can get the element by index directly Insertion - O(n) // in the worst case we need to resize the array to have a space for the new element Linked list: Access - O(n) // we need to reach the element ...


3

There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts. In general, if you think your audience might not be sure about ...


2

There are $2^{n^2}$ labelled directed graphs on $n$ vertices. Therefore, any such graph requires at least $n^2$ bits to represent it. So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs. If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ ...


Top 50 recent answers are included