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.

27 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
36 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
1
vote
1answer
22 views

Determing Big Oh Of Given Data

I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
1
vote
0answers
44 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
0answers
68 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: ...
1
vote
0answers
43 views

Big O notations of some functions

What is the big-O notation of the following functions : $\displaystyle\sum_{i=1}^n \left(\begin{array}{c} n-1\\ i \end{array}\right)\\\\ \displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\ n^{\...
1
vote
0answers
37 views

Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)

Here is a more readable version of the question: Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \...
0
votes
0answers
17 views

Time complexity of a recursive algorithm with two lists as parameters

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
0
votes
1answer
19 views

Prove that if g ( n ) ∈ ω ( 1 ) and f ( n ) ∈ o ( g ( n ) ) , t h e n 2 f ( n ) ∈ o ( 2 g ( n ) )?

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met? How would g ( n ) ∈ ω ( 1 ) affect our reasoning. ...
0
votes
0answers
29 views

The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
0
votes
0answers
20 views

Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ...
0
votes
0answers
28 views

Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this: ...
0
votes
0answers
48 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 ...
0
votes
1answer
34 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 &...
0
votes
0answers
34 views

Balanced vs Unbalanced KD-tree range search/query complexity

I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree. I see all these different articles where the same the complexity is O(sqrt(N)) where N is the ...
0
votes
2answers
51 views

Comparing growth of two sums of functions

Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?
0
votes
0answers
85 views

Time Complexity of Tabu Search Algorithm

I am trying to find the time complexity of Tabu Search. But I could not find any resources. Any need is appreciated.
0
votes
0answers
33 views

Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
0
votes
0answers
19 views

Question in regards to how an O(N^3) looks like using while/for loops

would the code below be considered O(N^3)? while (...) { while (...) { } while (...) { } }
0
votes
0answers
180 views

What is the Big theta of $(\log n)^2+2n+4n+\log n + 50$?

$f(n)=(\log n)^2+2n+4n+\log n + 50$ I am trying to mathematically prove that $f(n)$ falls under some time complexity big theta. My guess is that it is $(\log n)^2$ because it is the dominant term. I ...
0
votes
3answers
380 views

Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
0
votes
0answers
39 views

Summing big-O-notation

prove or disprove $$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$ I have no idea about where to begin. what are the theories which should be used here?
0
votes
0answers
33 views

How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
0
votes
0answers
27 views

Asymptotics and logarithms/exponents

We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ...
-1
votes
0answers
16 views

Checking if the spacetime complexity is the same for top-down and bottom up approach but different for runtime

Seeking help for the below bullet points. I will like to check whether the space-time complexity for both solutions is the same. Also, the run-time complexity for both is different. Here is the ...
-1
votes
1answer
32 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
votes
1answer
36 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 ...
-1
votes
1answer
19 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. ...