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
1answer
40 views

Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
0
votes
2answers
65 views

Θ, O, Ω, and how they relate to each other as subsets

I'm trying to better understand how Θ(n), O(n), and Ω(n) relate to each other as sets and want to make sure I'm on the right track. I get that Θ(n) ⊆ O(n) since Θ(n) is stronger and all of its ...
1
vote
1answer
23 views

What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?

What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$? I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $...
1
vote
1answer
54 views

Whether and how to distinguish two kinds of $O(1)$ speedup

Here is a very bad algorithm that computes $4n$ for an integer input. ...
1
vote
2answers
56 views

Who said first "In practice, log log N is at most (single digit number)?"

In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like In practice, $\log(\log(N))$ is at most 9. ...the idea being that even though the ...
0
votes
0answers
32 views

Is a polynomial function that is O(e^x) possible? [duplicate]

Are there any polynomial functions that are $O(e^x)$? Is this possible?
1
vote
4answers
77 views

Having a lot of trouble trying to reason the formal definition of Big O

My professor recently brushed over the formal definition of Big O: To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. ...
1
vote
1answer
46 views

What is the big-$O$ notation of a summation of logs where the arguments add to $n$?

For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ? I found this, but is not what I'm looking for.
7
votes
3answers
3k views

What are you allowed to move into the big O notation for it to be still correct?

Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct? For example: Is this $\log(O(n))= O(log(n))$ correct? Or is this correct $O(n)^2=O(n^...
1
vote
1answer
43 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
0
votes
1answer
56 views

Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
1
vote
1answer
54 views

Time Complexity Sigma Notation

Consider the following pseudo-code: counter = 0 for (k = 16; k > 0; k /= 2) for (j = 0; j < k; j++) counter++ I get that the time complexity is $...
0
votes
1answer
41 views

Why do we consider the + |V| in big-O notation in the time complexity of BFS

It is agreed upon that the time complexity of BFS is $O(|V| + |E|)$. Breath first search usually is used within a connected component. The connected component with the least $|E|$ given a fixed $|V|$ ...
1
vote
2answers
39 views

Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
1
vote
1answer
40 views
1
vote
2answers
78 views

Is $O(\log x) = O(1)$?

A colleague recently brought up this argument when we were talking about big-O runtime analysis and I've been unable to find why it is incorrect: Informally, the argument goes like this: "If the ...
0
votes
1answer
25 views

Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
0
votes
1answer
37 views

Return indices in the two sum problem

Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
0
votes
4answers
94 views

How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
0
votes
1answer
30 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
1
vote
3answers
85 views

Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?

Hello my question is that if i have two for loops inside each other like this: ...
1
vote
1answer
37 views

What is the Big-O Time Complexity of this code?

I was wondering if someone could please explain what the time complexity is for the code below. I think it would be $O(n)$ because the algorithm will take as much time to execute as there are elements ...
1
vote
1answer
49 views

If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?

I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$. Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true? I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, ...
1
vote
0answers
29 views

Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?

The given problem is from CLRS, exercise 4.3-2. Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n)) I decided to prove T(n) ≤ clog(n) and this is the result I got:...
0
votes
1answer
34 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
0
votes
1answer
31 views

simplified into asymptotic notation

I have a function that needs to be represented in theta form. The below is my answer. But the correct answer is 𝜃(n.2^n) Can someone please explain me how??
0
votes
1answer
33 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
1
vote
2answers
87 views

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$. I will omit what I have tried as it has not been useful.
10
votes
2answers
4k views

Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities? For example: $O(n) \cdot O(n) = O(n^2)$? UPDATE: The question came from my observation that different sources analyze their algorithms in different ways. For ...
2
votes
1answer
76 views

What is the computational complexity in big O notation of an algorithm computing n^n?

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
1
vote
2answers
130 views

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$? I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
5
votes
2answers
163 views

How does $Θ(\log(n!))=Θ(\log(n^n)$?

How does $Θ(\log(n!))=Θ(\log(n^n)$? I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the ...
1
vote
2answers
43 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
0
votes
2answers
165 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
0
votes
1answer
38 views

Apparently weaker form of big O notation

If instead of saying there exists some $C \in \mathbb{R}^{+}$ and $N \in \mathbb{N}$ such that for any $n \geq N$ we have $f(n) \leq Cg(n)$ we say that there is some $C \in \mathbb{R}^{+}$ and some ...
0
votes
2answers
119 views

Can't understand the $O$ notation for runtime of algorithms

In my book,the $O$-notation is given as: $$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$ ...
0
votes
0answers
33 views

Which is better $n^3\log n$ or $n^3$ [duplicate]

I am confused between $n^3\log n$ and $n^3$. Normally $n\log n$ is better than $n^3$ but what's about $n^3\log n$
1
vote
1answer
31 views

What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}. I found an ...
-1
votes
1answer
52 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
0
votes
1answer
56 views

How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?

Suppose, that I have a four-by-four matrix and I want to print each element of it. ...
3
votes
2answers
213 views

What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get ...
-2
votes
1answer
53 views

Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)

⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls? ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛) Found ...
1
vote
1answer
83 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
0
votes
3answers
68 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
0
votes
0answers
49 views

Average depth BST upper bound

I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
1
vote
1answer
87 views

For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
0
votes
3answers
144 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
1
vote
2answers
84 views

Silly question: what counts as a "unit of work" when computing big-Oh time complexity

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work". It says in the textbook that certain ...
2
votes
1answer
163 views

Shifted Big Os. How to say O((n+c)!) = O(n!)?

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is $nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$ Strictly, there is no constant factor that would make ...
0
votes
1answer
31 views

Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

$f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in ...

1
2 3 4 5 6