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
214 views

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
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

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

I have the following function. ...
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

Comparing growth of two sums of functions

Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?
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); } } ...