All Questions
55 questions
1
vote
1
answer
84
views
Does log(log(n)) grow asymptotically slower than log(n) / log(log(n))?
I'm trying to understand the asymptotic growth of relationship between log(log(n)) and log(n) / log(log(n)) as n -> infinity.
Specifically, I want to verify whether this statement is true or false:
...
- 13
4
votes
2
answers
130
views
How to Determining the Big O Complexity of a Recursive Function?
I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows:
fun (n) {
...
- 43
1
vote
1
answer
572
views
2
votes
6
answers
1k
views
Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?
Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations ...
- 579
0
votes
1
answer
30
views
Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?
I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
0
votes
1
answer
38
views
Conflicting definitions surrounding asymptotic notations. Please advise!
I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information.
For context, I believe I've understood the formal ...
- 113
4
votes
2
answers
255
views
An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is ...
- 141
5
votes
1
answer
94
views
Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?
How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
0
votes
2
answers
54
views
From these functions, how to determine which grows faster without graphing?
How are you intuitively able to tell the Big-Oh of the functions and what order they are on?
$$f(n)=3^n$$
$$g(n)=5^{3log_3{n}}$$
Note this is $5$ raised to $3log_3n$
$$h(n)=1024^{log_2n}$$
0
votes
2
answers
285
views
Confusion about asymptotic notations in math and computer science
The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science.
(...
- 3
0
votes
0
answers
135
views
Time complexity of Trie autocompletion (multiple variables in time complexity)
I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
- 1
4
votes
1
answer
108
views
Are "almost all" decidable languages not in P?
There's a famous classical circuit complexity result by Shannon that says almost all languages require exponential circuits [[1]], proven by comparing the number of distinct circuits of $n$ variables ...
- 71
2
votes
1
answer
452
views
Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.
This is similar to the notion ...
- 53
0
votes
2
answers
101
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
0
votes
0
answers
21
views
Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$
I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of
$$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
- 101
1
vote
1
answer
85
views
Comparing two functions rate of growth
This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question.
Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
- 189
1
vote
1
answer
676
views
How to prove that one problem belongs to class P?
Is there any formal method to prove that one problem belongs to Complexity Class $\mathbb{P}$?
For example, how can we prove that the problem of finding $n^k$ belongs to Class $\mathbb{P}$? We can use ...
- 165
0
votes
0
answers
125
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
1
vote
0
answers
84
views
Recursive algorithm running time?
I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm.
Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
1
vote
1
answer
124
views
What is the Runtime of this recursive algorithm?
I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
- 11
2
votes
3
answers
4k
views
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?
This is a question posted for extra practice (i.e., not for credit):
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.
I'm not sure ...
- 23
0
votes
1
answer
62
views
Do tasks that take up more memory/space always take more time?
Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep ...
- 113
7
votes
7
answers
6k
views
Is there a meaningful difference between O(1) and O(log n)?
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
- 171
2
votes
2
answers
1k
views
All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?
All the examples that I could think of satisfy the above ...
- 221
8
votes
4
answers
459
views
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
- 203
4
votes
2
answers
305
views
Finding which functions are bounded by $O(n^2)$
I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.
$f(n) = \sum_{i=1}^{n} n$
$f(n) = \sum_{i=1}^{n} i$
$f(n) = n + n^2$
$f(n) = 1$
I choose the ...
- 213
1
vote
1
answer
177
views
Is this computational complexity of the k-NN (custom distance) correct?
I read on a book that in general k-NN (no optimizations), given
$d$ dimensions
$n$ examples
every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
- 111
1
vote
1
answer
302
views
Counting letter frequency in array in O(1) with hash function
I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']
There are several ways to do this:
A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
- 167
-2
votes
1
answer
58
views
Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)
⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls?
⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)
Found ...
0
votes
2
answers
1k
views
Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
0
votes
1
answer
116
views
Finding the Big-O and Big-Omega bounds of a program
I am asked to select the bounding Big-O and Big-Omega functions of the following program:
...
- 213
2
votes
1
answer
214
views
Can all $O(n)$ problems be solved without nested loops?
There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
- 145
-2
votes
2
answers
192
views
Show that: $0.01n \log n - 2000n+6 = O(n \log n)$
Show that $0.01n \log n - 2000n+6 = O(n \log n)$.
Starting from the definition:
$O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
- 187
1
vote
1
answer
535
views
Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]
I have the following two functions
$f(n) = n\sqrt n + n \log n$
$\log_{100} n$
And I need to classify them into the followings:
$O(n)$, and/or
$O(n^2)$, and/or
$O(n^3)$, and/or
$O(n^{1.5})$, and/or
...
- 151
0
votes
0
answers
29
views
Computational complexity of described algorithm
Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks ...
- 109
0
votes
3
answers
105
views
Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
- 105
3
votes
2
answers
2k
views
Time complexity of functions that call each other
I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences ...
- 133
0
votes
0
answers
86
views
Question about asymptotic analysis comparing two functions
I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$
Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
- 173
1
vote
1
answer
88
views
Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:
A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$
In my opinion, it is not possible to define the best solution, since we don't know ...
- 173
4
votes
3
answers
452
views
Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?
I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063:
...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)...
- 39
0
votes
3
answers
2k
views
What is the average search complexity of perfect hashing?
The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
- 41
3
votes
1
answer
93
views
What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?
For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?
It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $...
- 537
1
vote
1
answer
208
views
Asymptotic relation between n! and (n+1)!
I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
- 19
3
votes
1
answer
4k
views
Time complexity of Dynamic Array via repeated doubling
When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
- 133
3
votes
0
answers
31
views
Bit complexity of computing the sign of an expression evaluated at an algebraic number
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
- 131
-1
votes
1
answer
118
views
What will be the computational complexity of a system with two pipelined algorithms?
A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
- 99
-1
votes
2
answers
494
views
Solve using master method $T(n) = n · T(n/2) + n^{\log n}$ [closed]
$T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log_{2}n}$.
$f(n) = n^{\log_{2}n}$
Number of leaves = $n^{\log_{a}b} = n^{\log_{2}n}$
CASE 2 (All level same)
$f(n) = \Theta(n^{\log_{b}a} {...
- 135
0
votes
1
answer
250
views
Relation between best case and average case complexity
I have two questions,
Does $T_\mathrm{best}(N) = O(f(N))$ imply that $T_\mathrm{avg}(N) = \Omega(f(N))$?
Does $T_\mathrm{avg}(N) = O(f(N))$ imply that $T_\mathrm{best}(N) = O(f(N))$?
Where,
\begin{...
0
votes
0
answers
40
views
Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?
Given this naive recursive function:
...
- 101
0
votes
1
answer
197
views
Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?
For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations
Calculating the $n^\text{th}$ root of an integer $x$,
$$
\sqrt[\leftroot{-3}...
- 467