Questions tagged [big-o-notation]
Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.
341
questions
0
votes
2
answers
26
views
Time complexity of algorithm involving function calls
Me again.
This time I have a more general question.
Suppose I have the following code snippet:
...
- 167
1
vote
1
answer
39
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 167
0
votes
1
answer
34
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 21
1
vote
0
answers
10
views
Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size
Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
- 11
0
votes
1
answer
33
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
0
votes
0
answers
34
views
Ranking functions by order of growth
Did I correctly rank these functions by order of growth? I ranked them from smallest to largest (left to right). I have to eventually prove this ranking, so just looking to make sure that I have the ...
0
votes
1
answer
61
views
Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n^2/\log n$, we have $f(n) = o(g(n))$?
Let $f(n) = n \cdot \sqrt n$ and $g(n)= \frac{n^2}{\log n}$. Why is $f(n) = o(g(n))$?
Could you please explain to me why this is so? I have tried l'Hôpital's rule but it doesn't add any ...
- 19
0
votes
1
answer
34
views
Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?
Which function grows faster:
$$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$
Which is true?
$f(n) = O(g(n))$
$g(n) = O(f(n))$
i.e., $f(n) = \Theta(g(n))$
none of the above?
For lower values of ...
- 1
5
votes
5
answers
3k
views
Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
0
votes
2
answers
47
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
3
answers
103
views
How to get a time estimation of an O(n) function to modern multi-core CPU time?
How to get an estimation of an O(n) function to modern multi-core CPU time? For instance, how can I find the time it takes to run an algorithm in a 4-core/8-core CPU when I know its O(n) ? I searched ...
- 135
1
vote
3
answers
97
views
Is $n^{1.03} = \Omega(n \log \log n)$?
We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How ...
- 117
-1
votes
3
answers
55
views
Can anyone help explain why the time complexity for this is O(n)
So ive already tried lookig at it but i just get O(nlogn) which is not correct
there were some clues like using a geometric series where 1/2+2/4+3/8+i/2^i<2 but idk how to implement that what ...
- 1
0
votes
2
answers
65
views
Subtracting Two same asymptotic values
I am dealing with two values $a$ and $b$ such that they grow at the same asymptotic rate, i.e., $O(\frac{1}{\sqrt{N}})$. I want to achieve a reasonable bound for the difference $a - b$. When I go into ...
-1
votes
1
answer
69
views
Verify $n\log n=\Theta(10n\log10n)$
How do I Verify that $n\log n=\Theta(10n\log10n)$
I think I need to prove that there exists $c_1,c_2>0$ such that $c_1.g(n)\le f(n)\le c_2.g(n)$
Step 1
$$
\log n\le \log 10n\implies f(n)=n\log n\...
- 139
0
votes
1
answer
29
views
Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :
...
- 1
3
votes
0
answers
67
views
What's the fastest known non-galactic algorithm for matrix multiplication of large matrices
"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
- 336
-1
votes
1
answer
45
views
Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2
I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method.
I was wondering if what I write below was correct and obviously the result:
$T(n) = n^2 + T(n-4) =...
- 121
0
votes
2
answers
160
views
When does Quicksort go from O(n log n) to O(n^2)?
Quicksort is O(n log n) average case, and O(n^2) worst case. The worst case occurs if one side of the pivot contains all of the elements and the other side contains none. However, I think the worst ...
1
vote
2
answers
92
views
Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$
We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a
constant $k<1$. We ...
0
votes
1
answer
62
views
Comparisons using Quicksort with the median as the pivot
Background
Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm:
Quicksort($a$):
(1) If length($a$) $...
- 103
0
votes
0
answers
16
views
Need help verifying the complexity of an algorithm [duplicate]
I have the following algorithm which takes as an input a non negative integer n :
i = n
while i > 0 do :
$\,$ $\,$ $\,$ $\,$i = i - 1
$\,$ $\,$ $\,$ $\,$j = 1
$\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
1
vote
1
answer
58
views
Finding max value in a min- heap
What is the time complexity of finding the maximal value in a minimum heap with n nodes?
Can I assume the maximal value is in one of leafs? If yes, there are ceil n/2 leafs. Does that make the time ...
- 11
0
votes
1
answer
33
views
if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))
Basically what i am trying to prove is this :
$f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $
I guess that if we take the definition of $f(...
1
vote
2
answers
44
views
If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?
It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).
Someone suggested that this question answers mine, which it doesn't. ...
- 23
1
vote
1
answer
392
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
0
votes
5
answers
215
views
Is $n^n$ is a big-oh n factorial
Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ?
Any suggestions how to prove/disprove this statement?
- 3
0
votes
1
answer
43
views
Trying to understand the time complexity of IDDFS
I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.
For BFS it is ...
- 1
-1
votes
2
answers
234
views
If f = O(h) and g = Ω(h) then f+g is?
Is the answer O(h) or Ω(h) for f+g?
My professor says its Ω(h), but I can't get it.
0
votes
2
answers
64
views
Comparison between big-Ω and ω notations
Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
- 121
0
votes
1
answer
38
views
Design an algorithm with linear complexity
Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.
Beyond the algorithm, what I can'...
- 121
0
votes
1
answer
65
views
Complexity of recursive function that calls itself with it's own return value
Given the following code:
int f3(int n)
{
if(n <= 2) return 1;
f3(1 + f3(n-2));
return n - 1;
}
I was trying to find the time complexity and I got this ...
0
votes
1
answer
37
views
the size of nice tree decomposition
Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation.
For a ...
- 318
-3
votes
2
answers
85
views
How to find the standard theta notation of this?
Hi i am practising standard theta notation:
How could i find the standard theta notation of the following :
2n + 3n^2(log n)^3 + 2
and
...
- 1
2
votes
1
answer
52
views
Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$
I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:
$$T(n)=aT(n/\...
- 121
-1
votes
2
answers
82
views
How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?
f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n))
I think we can prove this for omega but how can we prove it for Big oh ?
because if we simplify it to logn + logn <= logn +5 => logn<=...
0
votes
0
answers
45
views
Basic Clique Complexity Question
A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
0
votes
4
answers
238
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
2
answers
66
views
Derive complexity from recurrence relation
On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated:
$T(n) = 3 T(\frac{n}{2}) + cn + d$
And then, by invocation of ...
- 181
0
votes
3
answers
68
views
Help understanding the proof of the definition of Big-Theta based on limits
I was reading Kleinberg's and Tardo's book (especifically, this one) and, on page 38, these authors define the Big-Theta notation the following way:
Let $f$ and $g$ be two functions that $\lim_{n\to\...
- 3
0
votes
2
answers
131
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
1
answer
33
views
How can it be formally proved that $f \in O(⌊f ⌋)$
I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$
Here's what I've thought of so far,
we can set C = 10 and k = 1 and somehow prove ...
1
vote
3
answers
97
views
Upper bounding this expression
I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$
This ...
- 71
1
vote
1
answer
75
views
Proving this recurrence is $n \log n$
I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method.
$$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$
This is my attempt: I assume $T(n) \leq c n \log n$ and ...
- 71
1
vote
0
answers
51
views
Runtime of this algorithm
I have an algorithm with running time that satisfies
$$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
- 257
0
votes
1
answer
132
views
0
votes
1
answer
44
views
Understanding why this upper bound is tight
Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
- 257
0
votes
2
answers
99
views
Asymptotic Relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$
What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$?
The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because ...
- 11
0
votes
1
answer
566
views
1
vote
1
answer
81
views
Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?
Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{\log_b(a)}$ and $f(n)$. If the growth rate of $n^{\log_b(a)}$ is greater than the growth rate of $f(n)$ ...
- 113