time complexity

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/123

encourage image

There's no tags or description

Looks like no tags are added yet.

124 Terms

1
New cards

Notation: n = number of elements/nodes

O(1) = Constant time

2
New cards

Notation: O(log n)

Logarithmic time

3
New cards

Notation: O(n)

Linear time

4
New cards

Notation: O(n log n)

Linearithmic time

5
New cards

Notation: h

Height of the tree

6
New cards

Circular Queue (CLL) - Enqueue

O(1)

7
New cards

Circular Queue (CLL) - Dequeue

O(1)

8
New cards

Circular Queue (CLL) - Peek / Front

O(1)

9
New cards

Circular Queue (CLL) - Rear element

O(1)

10
New cards

Circular Queue (CLL) - IsEmpty

O(1)

11
New cards

Circular Queue (CLL) - Search

O(n)

12
New cards

Circular Queue (CLL) - Traversal / Display

O(n)

13
New cards

Circular Queue (CLL) - Count elements

O(n)

14
New cards

Circular Queue (CLL) - Space complexity

O(n)

15
New cards

Why is enqueue O(1) in Circular Queue CLL?

Only pointers are updated; no traversal is needed.

16
New cards

Why is dequeue O(1) in Circular Queue CLL?

Only pointers are updated; no traversal is needed.

17
New cards

DLL - Insertion at beginning

O(1)

18
New cards

DLL - Insertion at end with tail pointer

O(1)

19
New cards

DLL - Insertion at specific position

O(n)

20
New cards

DLL - Deletion at beginning

O(1)

21
New cards

DLL - Deletion at end with tail pointer

O(1)

22
New cards

DLL - Deletion at specific position

O(n)

23
New cards

DLL - Searching

O(n)

24
New cards

DLL - Forward traversal

O(n)

25
New cards

DLL - Backward traversal

O(n)

26
New cards

DLL - Accessing element by position

O(n)

27
New cards

DLL - Updating element by position

O(n)

28
New cards

DLL - Space complexity

O(n)

29
New cards

Why is DLL insertion at beginning O(1)?

Only a fixed number of pointers are updated.

30
New cards

Why is DLL deletion at beginning O(1)?

Only a fixed number of pointers are updated.

31
New cards

When is DLL insertion at end O(1)?

When a tail pointer is maintained.

32
New cards

When is DLL deletion at end O(1)?

When a tail pointer is maintained.

33
New cards

Why is DLL insertion at a specific position O(n)?

The position must first be located by traversal.

34
New cards

Why is DLL deletion at a specific position O(n)?

The position must first be located by traversal.

35
New cards

Circular Array Deque - Insert at front

O(1)

36
New cards

Circular Array Deque - Insert at rear

O(1)

37
New cards

Circular Array Deque - Delete from front

O(1)

38
New cards

Circular Array Deque - Delete from rear

O(1)

39
New cards

Circular Array Deque - Get front element

O(1)

40
New cards

Circular Array Deque - Get rear element

O(1)

41
New cards

Circular Array Deque - Search

O(n)

42
New cards

Circular Array Deque - Traversal / Display

O(n)

43
New cards

Circular Array Deque - Access by index

O(1)

44
New cards

Circular Array Deque - Space complexity

O(n)

45
New cards

DLL Deque - Insert at front

O(1)

46
New cards

DLL Deque - Insert at rear

O(1)

47
New cards

DLL Deque - Delete from front

O(1)

48
New cards

DLL Deque - Delete from rear

O(1)

49
New cards

DLL Deque - Get front element

O(1)

50
New cards

DLL Deque - Get rear element

O(1)

51
New cards

DLL Deque - Search

O(n)

52
New cards

DLL Deque - Traversal / Display

O(n)

53
New cards

DLL Deque - Access by position

O(n)

54
New cards

DLL Deque - Space complexity

O(n)

55
New cards

Circular Array Deque vs DLL Deque - Access by index

Circular Array: O(1); DLL: O(n).

56
New cards

Why is insertion at both ends O(1) in a DLL Deque?

Both front and rear pointers are directly available.

57
New cards

Binary Tree - Insertion (general tree)

O(n)

58
New cards

Binary Tree - Deletion (general tree)

O(n)

59
New cards

Binary Tree - Searching

O(n)

60
New cards

Binary Tree - Inorder traversal

O(n)

61
New cards

Binary Tree - Preorder traversal

O(n)

62
New cards

Binary Tree - Postorder traversal

O(n)

63
New cards

Binary Tree - Level order traversal

O(n)

64
New cards

Binary Tree - Finding height

O(n)

65
New cards

Binary Tree - Finding maximum element

O(n)

66
New cards

Binary Tree - Finding minimum element

O(n)

67
New cards

Binary Tree - Counting total nodes

O(n)

68
New cards

Binary Tree - Counting leaf nodes

O(n)

69
New cards

Binary Tree - Space complexity

O(n)

70
New cards

Why is binary tree traversal O(n)?

Every node is visited exactly once.

71
New cards

Does a general binary tree guarantee O(log n) searching?

No. Searching can require visiting every node.

72
New cards

BST - Insertion (best / average case)

O(log n)

73
New cards

BST - Insertion (worst case)

O(n)

74
New cards

BST - Deletion (best / average case)

O(log n)

75
New cards

BST - Deletion (worst case)

O(n)

76
New cards

BST - Searching (best / average case)

O(log n)

77
New cards

BST - Searching (worst case)

O(n)

78
New cards

BST - Finding minimum (best / average case)

O(log n)

79
New cards

BST - Finding minimum (worst case)

O(n)

80
New cards

BST - Finding maximum (best / average case)

O(log n)

81
New cards

BST - Finding maximum (worst case)

O(n)

82
New cards

BST - Finding inorder successor (best / average case)

O(log n)

83
New cards

BST - Finding inorder successor (worst case)

O(n)

84
New cards

BST - Finding inorder predecessor (best / average case)

O(log n)

85
New cards

BST - Finding inorder predecessor (worst case)

O(n)

86
New cards

BST - Inorder traversal

O(n)

87
New cards

BST - Preorder traversal

O(n)

88
New cards

BST - Postorder traversal

O(n)

89
New cards

BST - Finding height

O(n)

90
New cards

BST - Space complexity

O(n)

91
New cards

Why are BST search operations O(log n) on average?

The tree is reasonably balanced and its height is approximately log n.

92
New cards

Why are BST operations O(n) in the worst case?

The BST becomes skewed, behaving like a linked list.

93
New cards

What is the height of a balanced BST approximately?

O(log n)

94
New cards

What is the height of a skewed BST approximately?

O(n)

95
New cards

AVL - Insertion

O(log n)

96
New cards

AVL - Deletion

O(log n)

97
New cards

AVL - Searching

O(log n)

98
New cards

AVL - Finding minimum

O(log n)

99
New cards

AVL - Finding maximum

O(log n)

100
New cards

AVL - Finding height recursively from scratch

O(n)