Skip to main content

# 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.

370 questions
Filter by
Sorted by
Tagged with
0 votes
3 answers
108 views

### Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
0 votes
1 answer
29 views

0 votes
0 answers
52 views

### Graph Problem Time Complexity

I'm trying to devise an algorithm for the following prompt from LeetCode's daily challenge: You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[...
-1 votes
3 answers
126 views

### Time complexity of algorithm involving function calls

Me again. This time I have a more general question. Suppose I have the following code snippet: ...
0 votes
1 answer
27 views

### Recurrence relation simplification

I have initial condition $𝑛_1=2, 𝑣_1=1$, and the given recurrence relations: $𝑛_{𝑖+1}=2𝑛_𝑖,$ $𝑣_{𝑖+1}=2𝑣_𝑖+\frac{1}{2} 𝑛_𝑖$ I need to show that that, $v_i=\Theta(n_i\log⁡ n_i).$ I observe ...
0 votes
1 answer
105 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
0 votes
1 answer
63 views

### Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
0 votes
1 answer
57 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
1 answer
49 views

0 votes
1 answer
57 views

### Big O Notation, Why do we ignore everything inside the log?

Okay, so I understand implicitly why we might write f(n) = log 3n = O(log n) but I don't really understand why lets say ...
2 votes
1 answer
33 views

### Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
1 vote
1 answer
269 views

### Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
1 vote
0 answers
37 views

### Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size

Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
1 vote
3 answers
680 views

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

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
0 votes
0 answers
86 views

### Ranking functions by order of growth

Did I correctly rank these functions by order of growth? I ranked them from smallest to largest (left to right). I have to eventually prove this ranking, so just looking to make sure that I have the ...
0 votes
1 answer
77 views

### Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n^2/\log n$, we have $f(n) = o(g(n))$?

Let $f(n) = n \cdot \sqrt n$ and $g(n)= \frac{n^2}{\log n}$. Why is $f(n) = o(g(n))$? Could you please explain to me why this is so? I have tried l'Hôpital's rule but it doesn't add any ...