All Questions
Tagged with complexity-theory asymptotics
145 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
1
vote
2
answers
61
views
Calculating complexity for recursive functions with substitution method (Big O notation)
(https://i.sstatic.net/oTCBO87A.png)
I have to calculate the complexity of this algorithm using the substitution method but I don't understand how to do it.
I'm guessing that ...
- 11
1
vote
1
answer
46
views
Is $n\log n + n\log \log n = \Theta(\log n)$?
To show $n\log n + n \log(\log n) = \Theta(\log n)$. Is this even correct? It can be easily shown that, $n \log n + n \log(\log n)$ is $O(n\log n)$ and also $\Omega(n\log n)$, with constants $2$ and $...
1
vote
1
answer
812
views
How can I prove that '+' is same as max?
I know that, $\max(m, n) = O(m+n)$.
But my teacher uses, $$m+n=\Theta(\max\{m, n\}).$$
Anyone explain me why the above expression is true.
user150715
1
vote
1
answer
31
views
Emphasizing the Coefficients of the Leading Order and Using Big O Notation for the Remainder
I am trying to understand the correct application of Big O notation to polynomial expressions, including terms with negative coefficients. For example, consider the polynomial $2n^3-2n^2+n+1$, where $...
4
votes
2
answers
129
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
0
votes
0
answers
25
views
Relation between running time of Insertion sort and number of inversions
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
Consider Insertion sort
...
- 1
4
votes
2
answers
158
views
What does $o_n(1)$ mean?
I'm trying to read the following article, and in the abstract they write:
Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
- 43
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 ...
1
vote
1
answer
572
views
2
votes
2
answers
93
views
Big O notation of $O(n/(m-n))$
I'm new to the complexity theory and have a basic question about the big-O notation that I encountered.
I came across a complexity of $O\big(\frac{n}{m-n}\big)$, where both $n$ and $m$ are independent ...
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
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}$$
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
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
0
votes
4
answers
2k
views
What is the lower bound of n factorial
The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!.
We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
- 21
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
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
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
5
votes
1
answer
93
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
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
-2
votes
1
answer
64
views
Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))
How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
- 1
2
votes
1
answer
451
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 ...
3
votes
2
answers
373
views
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
- 145
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
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
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 ...
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
1
vote
1
answer
160
views
Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method
Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$.
I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.
Try 1:
If we ...
- 145
0
votes
0
answers
37
views
Sum of asymptotic notations
Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$?
Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
- 13
0
votes
1
answer
32
views
Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.
Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
- 13
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
6
votes
1
answer
287
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 163
0
votes
1
answer
50
views
Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
- 219
-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
1
answer
96
views
Having trouble understanding blatantly non-private definition because of Little-o notation
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.
...
- 3
0
votes
1
answer
129
views
Douglas-Peucker line simplification algorithm time complexity
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points ...
- 139
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
1
vote
1
answer
129
views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
- 123
1
vote
1
answer
39
views
A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea: i think because of for any $f:N\rightarrow N$, and $g:...
user132812
1
vote
2
answers
110
views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
- 13
1
vote
1
answer
390
views
How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables
I am reading a proof that the Subset Sum decision problem is NP-complete.
I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$.
...
- 108
1
vote
1
answer
78
views
Asymptotic notation between two sets of variables
I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its ...
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
2
answers
599
views
Trouble finding average case of a find max algorithm
I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.
...
- 23
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
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
0
votes
1
answer
50
views
Doing induction on recurrences correctly
I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^...
- 155
0
votes
2
answers
91
views
Failing to solve a recurrence by induction
My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which ...
- 155