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.

Filter by
Sorted by
Tagged with
1 vote
2 answers
37 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. ...
1 vote
1 answer
52 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
4 answers
80 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?
0 votes
1 answer
30 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 ...
0 votes
2 answers
56 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
61 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))
  • 111
0 votes
1 answer
36 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'...
  • 111
0 votes
1 answer
44 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
28 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 ...
  • 176
-3 votes
2 answers
74 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
28 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/\...
-1 votes
2 answers
37 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
41 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
78 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. ...
0 votes
2 answers
40 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 ...
  • 131
0 votes
3 answers
35 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\...
0 votes
2 answers
59 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
32 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
1 answer
71 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 ...
1 vote
1 answer
74 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 ...
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
89 views

search for the next prime number more efficiently?

...
  • 13
0 votes
1 answer
36 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
65 views

Asymptotic Relationship between 1/n and 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
141 views

Why is the complexity of BFS O(V+E) instead of O(V*E)?

CLRS pseudocode: ...
1 vote
1 answer
73 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
1 vote
2 answers
60 views

Asymptotics of $F(n) = n \times n^{\log_32}$

Is the complexity of $F(n) = n \cdot n^{\log_3 2}$ allowed to be written as $O(n)$, or must you specify and say $O(n^{1.63})$, or even must you write $O(n^2)$ since it is an upper bound?
0 votes
0 answers
41 views

Can 0 be a tight upper bound of -4n?

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2). We can take it ...
11 votes
3 answers
2k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
0 votes
2 answers
70 views

What is the asymptotic runtime of the below equation?

What is the asymptotic of ${n \choose 3} \log ^4n$ ? I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?
  • 135
-3 votes
1 answer
55 views

Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))

How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
  • 1
1 vote
0 answers
39 views

Algorithms with different upper and lower bounds

I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
  • 11
-1 votes
2 answers
326 views

what is the time complexity of this while loop nested in a for loop?

I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length: ...
  • 1
0 votes
1 answer
25 views

Landau Notation/Big O notation

In our class the following exercises/examples were given: Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that: $n^{2/3} \in \Omega(log^8(n))$. Then in the Solution ...
  • 185
1 vote
1 answer
36 views

Are there any "fast" algorithms for defragmenting memory?

This is about memory, not files or filesystems. So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later ...
  • 129
-1 votes
1 answer
75 views

How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction, $$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases} $$ Here, $\...
  • 169
0 votes
1 answer
68 views

Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?

Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
  • 151
0 votes
1 answer
30 views

How to show that $n^2 = O(f(n-1)+n)$?

This is from Ex. 0.2.(b) from "Computational Complexity" by Arora and Barak (2009): One needs to find a non-recursively defined function $g$ s.t. (1) $f = O(g)$ and (2) $g = O(f)$, where $f(...
  • 103
0 votes
0 answers
33 views

Baby step giant step algorithm complexity calculation

My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
0 votes
1 answer
50 views

Big O- and Omega-Notation for functions

I want to find out how to check, if the following relationships are true or false. f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false; f(n) = 3n^2; g(n) = 9^...
  • 3
1 vote
0 answers
39 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
0 votes
4 answers
68 views

Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
0 votes
5 answers
184 views

Prove big O notation for $\log(n!)$ without applying Stirling's formula

I want to prove that, $$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$ The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow. Can ...
0 votes
2 answers
97 views

Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?

I'm following an online course about Complexity and I'm learning a lot of stuff. I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here. ...
-1 votes
1 answer
44 views

Complexity of T(n)=2T(n-1)

I built a recursion tree like this: 0 / \ 0 0 /\ /\ ... ... So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum_{i=0}^{n}...
  • 1
0 votes
2 answers
59 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
1 vote
1 answer
88 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis: Imagine that the following big-O expressions ...
1 vote
3 answers
67 views

Difference between an exact and Big O Notation for worst case runtime

I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm. This is what I'm struggling to ...
1 vote
1 answer
643 views

Time complexity when taking certain elements and iterating over them?

I'm trying to gain a better understanding of Big O. Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating ...
-2 votes
1 answer
51 views

What is the BigO of a C# function when runtime is 3n - logn + 1

I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
  • 5

1
2 3 4 5
7