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.
235
questions
1
vote
2answers
214 views
0
votes
1answer
69 views
How to calculate the runtime of a following code?
Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?
...
1
vote
1answer
44 views
Big-O of iterating through nested structure
While trying to understand complexity I run into an example of going through records organized in following way:
...
-1
votes
1answer
46 views
big theta prove
Prove that $3n^3 - 6n^2 + 9n - 9\log n \in \Theta(n^3)$ using
So, how can I prove this by big theta definition? I don't what I should do with the log function
1
vote
2answers
106 views
Can $n = O(n^2)$?
I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below:
Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real ...
0
votes
1answer
66 views
How to calcualte the Big-O complexity of the following algorithm?
I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).
<...
2
votes
5answers
1k views
Big O notation for Average case in Linear search
Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
3
votes
3answers
184 views
What is the complexity of $i^i$?
What is the complexity of the following algorithm in Big O:
for(int i = 2; i < n; i = i^i)
{
...do somthing
}
I'm not sure if there is a valid operator to ...
0
votes
0answers
31 views
Time complexity about Maximum subarray
I recently came across a function called the strawman algorithm which the pseudo code looks like this:
...
1
vote
2answers
151 views
Solving unusual recurrence with two variables
I have the following recurrence relation:
$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$
With the following base cases (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$...
2
votes
2answers
156 views
How does f(n) < cg(n) specify time?
I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:
$O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
0
votes
1answer
44 views
Intro to Algorithms: asymptotic function analysis
I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can ...
-1
votes
1answer
84 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
-1
votes
1answer
81 views
How to know if time complexity is O(n+m) or O(n*m)
I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m
Is the time complexity of the following algo O(n+m) or O(n*m)
Can you please point me to a ...
0
votes
3answers
575 views
Sum rule for Big-O with equal complexity-functions?
One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined ...
1
vote
0answers
46 views
Complexity Values for Specific Code/Functions
(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
1
vote
1answer
43 views
How to solve recursion with two separate converges rates
What is the correct way to solve the following recursion:
$T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$
Or basically any recursion that has two parts which converge in a different rate.
I'm trying to get ...
0
votes
1answer
84 views
How do you calculate the running time using Big-O notatation?
I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():
...
1
vote
0answers
186 views
What is Big O of a loop with square root inside?
Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code:
...
0
votes
2answers
401 views
Time complexity of printing prime numbers within a range?
I've written an answer to this question, which asks about the following:
What is the time complexity for the given code that prints prime numbers from start to <...
5
votes
1answer
74 views
Does big-Oh impose an ordered partition on the set of the "usual" functions?
The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not ...
0
votes
0answers
50 views
Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$
I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$.
Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
1
vote
1answer
40 views
Find position in array where element-wise multiplication with string of 1 and 0s results in max value
I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in ...
1
vote
2answers
81 views
How to determine if given “complex” time complexity is $O(n^2)$?
If a given time complexity, such as these:
$(n + \log n) * \sqrt{n+\log n}$
$n * (200 + \log^2 n)$
$(7+n^3)\log(n^5)$
is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
0
votes
3answers
269 views
Big O vs Big $\Theta$ during coding interview
Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$.
From the book "Cracking the coding interview":
"...
2
votes
1answer
29 views
Order notation subtractions in Fibonacci Heap
Can order notation on its own imply:
$O(D(n)) + O(t(H)) - t(H) = O(D(n))$
My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
0
votes
1answer
23 views
How to find the square with the highest total sum
I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most.
For ...
0
votes
3answers
64 views
Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2
If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
0
votes
1answer
50 views
one for loop wraps 2 indexof method, what is the time efficiency?
I'm confused about how to know the time / space efficiency.
If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...
0
votes
1answer
86 views
How to prove Big-O when $F(N)$ is even or odd
If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
-1
votes
1answer
46 views
Analysis of kd-tree, how is the vertical line L's intersect areas equivalent to sqrt(N)?
I'm trying to understand how the number of intersected areas by a vertical line in a KD-tree is equivalent to sqrt(n)
If you draw a balanced KD-tree with 7 nodes.
And then draw a vertical line l.
...
1
vote
1answer
118 views
Time complexity of code running at most summation(N) times in a loop
Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration:
...
1
vote
2answers
376 views
Analysis of Dijkstra algorithm's (Lazy) running time
I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation.
But when we do the math we get ...
0
votes
1answer
25 views
2
votes
1answer
64 views
Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?
Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.
In the 2-dimensional case it's fairly ...
2
votes
3answers
80 views
Little O notation relationship
Given the functions $𝑓(𝑛)=𝑛^{n}$ and $𝑔(𝑛)=10^{10n}$, I am trying to establish the following relationship: $𝑓(𝑛)\notin o(𝑔(𝑛))$.
I know to show for the opposite, $𝑓(𝑛)\in o(𝑔(𝑛))$, I ...
1
vote
1answer
67 views
Solving a multivariate equation for asymptotic complexity
I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation
$$\begin{align}
T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\
T(m,\ ...
0
votes
1answer
42 views
Time complexity analysis of 2 arbitrary algorithms - prove or disprove
We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.
We denote the worst time complexity of each ...
1
vote
2answers
241 views
What is the big-$O$ notation of a summation of a log?
For:
$$\sum^{n+m}_{i=n} \log(i)$$
I'm wondering what the big O notation is and how to prove it...
I believe that we can also write this as
$$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$
...
1
vote
1answer
80 views
Big theta notation
I'm trying to figure out the following problem:
If algorithm $A$ has a big theta notation of $n^3$ and algorithm $B$
has a big theta notation of $n^2$, there might be an infinite number
of ...
0
votes
7answers
438 views
What is the time complexity Big-O of this algorithm?
What is the time complexity Big-O of this algorithm?
, The first assumption it's O(N * lg N) but it is not correct, why?
...
1
vote
2answers
104 views
Time complexity of Vertex Cover vs Clique for fixed k
I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm ...
1
vote
3answers
68 views
5
votes
2answers
99 views
Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?
I have a simple quesiton:
It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH.
also
there is a result that says APSP can ...
1
vote
1answer
17 views
Big O notation space/time
I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read ...
1
vote
2answers
91 views
What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?
Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.
1
vote
1answer
42 views
1
vote
2answers
61 views
Algorithms: Determining Asymptotic Notation from a given execution time
I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it.
Question 1: An Algorithm with ...
2
votes
2answers
73 views
Complexity of $O(\log(n^n))$ vs $O(\log(n!))$
Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?
And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$...
2
votes
1answer
53 views
"Unrolling" a recurrence relation
int function(int n)
{
int i;
if (n <= 0) {
return 0;
} else {
i = random(n - 1);
return function(i) + function(n - 1 - i);
}
}
...
