New answers tagged runtime-analysis
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
