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.

Filter by
Sorted by
Tagged with
1
vote
2answers
21 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
18 views

Big-O: Why is the time complexity of these loops O(N)?

I have the following function. ...
2
votes
1answer
46 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
60 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 ...
-2
votes
0answers
20 views

Find O(f(n) for the given functions [duplicate]

(1). f(n) = 2^n + 6logn (2). f(n) = n^3 + 42n^2 + 0n^4 + 2nlogn (3). If f(n) = 4000 + logn my answer is O(2^n) O(n^3) O(logn) is that correct or if you have different answer please.
1
vote
1answer
44 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
21 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
32 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
31 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
273 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? ...
0
votes
1answer
40 views

Big O Tires Question?

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.) What's the runtime of this code? ...
0
votes
0answers
17 views

Big O Calculating Runtime [duplicate]

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." What's the runtime of this code? ...
1
vote
2answers
27 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 ...
0
votes
2answers
43 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
14 views

Is the usage for asymptotic notation for these algorithms correct? [duplicate]

So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I'm trying to grasp how to utilise this in the best way when representing algorithms ...
5
votes
2answers
79 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
14 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
62 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.
0
votes
0answers
44 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.
1
vote
2answers
46 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
67 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
24 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); } } ...
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)$ ...
1
vote
1answer
42 views

Big O of rational function using the definition

I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$. I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction. How would I go about ...
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^{\...
0
votes
1answer
134 views

Remove range of keys from Binary Search Tree in O(s+h)

I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h) where s is the number of keys to remove and h is the height of the tree. Attempted ...
1
vote
2answers
146 views

What is the worst-case big-O time complexity for this code?

I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so ...
0
votes
1answer
28 views

Growth of exponential functions according to the big O notation

I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O ...
12
votes
5answers
2k views

Does it make sense to say Big Theta of 1? Or should we just use Big O?

Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$? Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
1
vote
1answer
30 views

Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
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
63 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 ...
2
votes
4answers
105 views

Is this big O notation format correct? $3^n = 2^{(O(n))}$

I am completing a university exercise deciding whether big notations are true or false. I am stuck on this question : $$3^n = 2^{(O(n))}$$ I want to answer False as the format looks incorrect and ...
2
votes
0answers
29 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 ...
0
votes
2answers
39 views

Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...
1
vote
1answer
41 views

Determining asymptotic notation of a complex function

$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
1
vote
0answers
30 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
2answers
67 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
1answer
19 views

Asymptotic growth of a function containing a sum

How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
1
vote
1answer
67 views

Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$. Given this pseudocode: ...
0
votes
2answers
78 views

Is this program O(n^2logn) or O(nlog^2(n))?

I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely. ...
0
votes
1answer
28 views

Big-O Notation: Runtime Analysis

I have a problem with an exercise, I have to analyze the following For-Loops Then I have to write down the explicit notation, my problem is that I don't know how to get the right m. I tried this but ...
2
votes
1answer
96 views

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$? I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
3
votes
1answer
137 views

Is O(n log n) exponential speedup over O(n^2)?

I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
2
votes
1answer
112 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
3
votes
1answer
92 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. IΒ΄ve made a program to check this statement and it ...
2
votes
2answers
259 views

Why is n log n dominated by n log^2 n?

Does the rule of $n ^ a$ dominate $n ^ b$ if $a > b$ apply here as well? My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.
1
vote
1answer
68 views

About Big O properties

Suppose I have something like the following: $f(x) = g(x) + O(x^n)$ And I apply a power $m$ to both sides $f(x)^m = g(x)^m + \cdots + O(x^n)^m$ My question is whether the following is well ...
1
vote
0answers
35 views

Which function grows faster: N Log N or N^(1+Ρ/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.